Why does $f(n) = O(n^2)$?

73 Views Asked by At

My book says:

For example, consider $f_1(n) = n$ and $f_2(n) = n^2+1$. Clearly, the former is $O(n^2)$ and the latter is $O(n^3)$.

I thought they would both be $O(n)$ and $O(n^2)$ respectively. Why is it "clear" that these two have the complexity that the author says?

1

There are 1 best solutions below

7
On BEST ANSWER

If $f(n)$ is $O(n^2)$ (which is true) this does not mean that $f(n)$ grows proportional to $n^2$. It means that $f(n)$ is bounded above by some quantity proportional to $n^2$.

I think you also misunderstand what “clear” means in this technical context. It does not mean “you can see it just by looking”. Instead it means “You can verify the claim in a minute or two, by applying the definition.” But you must know what the definition is in order to apply it, and then you have to actually make the argument.

Let's see what that looks like in this case. The claim is that $f(n)=n$ is $O(n^2)$. This means that there exist constants $C$ and $k$ such that $$\text{whenever $n>C$, we have $n < kn^2$}.$$

To prove this, we need to find $k$ and $C$ for which the claimed property is true. Since $kn^2$ ought to increase much faster than $n$, let's try $k=1$, so we want $n<n^2$ whenever $n>C$. Then $C=0$ doesn't work, but $C=2$ ought to do. And in fact $n<n^2$ for all $n>2$, so we win.

That wasn't too hard, and there are lots of similar choices of $k$ and $C$ that would work as well. (We could have taken $k=C=1,000,000$, for example.) Sometimes you need a tricky argument to show that $f(x)$ is $O(g(x))$, but here we could just pick out the numbers. That's what ‘clear’ means: not that you can see it without any argument, but that the argument was easy to find.