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?

  • 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)$.2012-11-27
  • 0
    $7x^2$ is in $O(x^2)$ *and* $O(x^3)$. In fact, it's in $O(x^n)$ for any $n \ge 2$.2012-11-27
  • 0
    @caughtinalandslide: Why the discrete-mathematics tag?2012-11-27
  • 0
    I'm studying it under a course called Discrete Mathematics for Computer Science, hence I tagged it such.2012-11-27
  • 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