0

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?

apnorton
  • 17,706
user6607
  • 381

1 Answers1

2

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.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • Why wouldn't $C=1$ work? If $n >1$ (say 2), then it's true that $2<2^2$. – user6607 Sep 29 '14 at 18:42
  • You're right, $C=1$ would work also. But $C=0$ wouldn't. – MJD Sep 29 '14 at 18:47
  • The thing is, I don't want to verify the claim that $f(n)=O(n^2)$. If someone gives me a function $f(n) = n$ and tells me to give the big oh, how would I do that? – user6607 Sep 29 '14 at 18:47
  • 2
    It depends. Is that person the boss at your programming job, or is that person the grader in a computer science course? Because programmers abuse the terminology and mean something different than what the actual definition is. In programmer lingo $O(f(x))$ actually means something more like $\Theta(f(x))$, but programmers do not realize this. If the grader in your class were to ask the question “Give the big oh of $f(n)=n$” you should complain, because it is a nonsensical question; $f$ is $O(n)$, but it is also $O(n^2)$ and $O(n!3^{27n+\log_\ast n})$. – MJD Sep 29 '14 at 18:51
  • (But you should also note that the common parlance among programmers is very informal, and not entirely consistent; programmers will cheerfully refer to a quantity as $O(2^n)$ when in fact it is $O(3.8^n)$, and they are simply wrong. But the programmer doesn't care because both $\Theta(2^n)$ and $\Theta(3.8^n)$ are practically the same for programmers: they both belong to the complexity class of “too slow to be useful”.) – MJD Sep 29 '14 at 18:55
  • Okay. And when we say something is "bounded above" by some constant times $n^2$, what we mean is that the "some constant times $n^2$" is greater than that function? – user6607 Sep 29 '14 at 18:57
  • Yes. ${}{}{}{}{}$ – MJD Sep 29 '14 at 19:36