Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<x^3$,
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?

share|improve this question
5  
You are right, $7x^2$ is $O(x^2)$, But it is also $O(x^3)$, and $O(x^{17}$. Just like $1$ is $\lt 1.01$, but also $1\lt 12$, and $1\lt 1000$. Saying $7x^2$ is $O(x^2)$ "says more" than saying $7x^2$ is $O(x^4)$. –  André Nicolas Nov 27 '12 at 8:02
    
$7x^2$ is in $O(x^2)$ and $O(x^3)$. In fact, it's in $O(x^n)$ for any $n \ge 2$. –  Snowball Nov 27 '12 at 8:02
    
@caughtinalandslide: Why the discrete-mathematics tag? –  Dennis Gulko Nov 27 '12 at 8:04
    
I'm studying it under a course called Discrete Mathematics for Computer Science, hence I tagged it such. –  caughtinalandslide Nov 27 '12 at 8:06
    
@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. –  caughtinalandslide Nov 27 '12 at 8:07

2 Answers 2

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)$.

share|improve this answer

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^+}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.