Big Oh notation of $7x^2$, confused
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?
$\endgroup$ 52 Answers
$\begingroup$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)$.
$\endgroup$ $\begingroup$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^+}$.
$\endgroup$
