6
$\begingroup$

I'm supposed to figure out the Big-Oh notation of $7x^2$. Take a look at this.

Now this says:

Show that $7x^2$ is $O(x^3)$ When $x>7, 7x^2,
So let $C=1$ and $k=7$, we see $7x^2$ is $O(x^3)$. Alternatively, when $x>1, 7x^2<7x^3$ and so that $C=7$ and
$k=1$, we have the relationship $7x^2$ is $O(x^3)$

By this logic shouldn't the Big Oh of $7x^2$ be: $7x^2<8x^2$ $7x^2 \in O(x^2)$ with C=8 and k=1? Since $7x^2$ is obviously less than $8x^2$ for each $k>=1$. Why do we need $x^3$?

At the same time the link says

Let $f(x)=a_nx^n+…+a_1x+a_0$, where a0, a1, …, an-1, an are all real numbers, then f(x) is $O(x^n)$

And doesn't the above mentioned rule specifically state that for a polynomial of degree n, the big oh will be $O(x^n)$?

What am I missing here?

  • 0
    @Andre and Snowball: Okay, that makes sense. Wonder why this fact isn't clearly explained in the example that $O(x^3)$ isn't the most 'efficient' Big Oh notation for $7x^2$. And I've seen this example in 2-3 different places.2012-11-27

2 Answers 2

4

As the comments already say, you are right in saying that $7x^2$ is $O(x^2)$. But it is also $O(x^3)$ or $O(x^n)$ for $n \geq 2$. Informally, the big-Oh notation gives an upper bound on how fast the given function grows. So, $7x^2$ grows as a quadratic function (giving $O(x^2)$), but it also grows slower than a cubic function (giving $O(x^3)$).

However, this generic definition is all right, but not very useful in general. If, for example, you say that $7x^2$ is $O(x^5)$ and $7x^4$ is $O(x^5)$, it does not give you any idea about how $7x^2$ compares to $7x^4$. The $O(x^5)$ gives a very loose upper bound to the asymptotic growth of these functions. In other courses you will learn about the use of big-Oh notation. It gives you an idea about how efficient an algorithm is. That is why, you need to give the big-Oh complexity as close to the lowest upper bound as you can. So, you will almost always say $7x^2$ is $O(x^2)$, even if, according to the strict definition, it is also $O(x^3)$.

0

This notation has always confused me before, because computer science professors always seem to teach the concept incorrectly. No doubt textbooks teach it wrong too.

If a function $f(x)$ satisfies the following equality:

$f(x) = O(x^2)$

Then the following must also be true:

$f(x) = O(x^3)$

If the steady-state growth of $f(x)$ is bounded by $x^2$, then it is also bounded by $x^3$. Why is this? Because as we look at larger and larger values of $x$, the polynomial $Ax^3$ will eventually surpass $Bx^2$ for $A$, $B$ $\in \mathbb{R^+}$.