Question

Why is 2n^2 = O(n^3) ?

This is given as an example of big O notation in the MIT OCW Introduction to Algorithms (SMA 5503) course. It's in lecture 2 around minute 3. My calc background is extremely shaky, and I really don't understand what's going on there.

Answer 1

Specifically, it looks to me like that should be O(n^2) --I thought that's what dropping the leading terms means.

Answer 2

It is O(n^2)

Answer 3

hmm. Then the professor must've made a mistake. Thanks!

Answer 4

Well

Answer 5

Recall that big 0 is an upper bound

Answer 6

So technically everything that's O(n) is also O(n^2) and all higher values?

Answer 7

Yeah, but we'd like to have as tight a bounds as possible

Answer 8

I'm watching the vid to see if I can figure out why he was using that

Answer 9

yeah he just made a mistake.

Answer 10

yeah, I was really confused. It seems like the point of big O notation is to try to describe the growth of functions for arbitrarily large inputs, but calling that O(n^3) only seems to describe the function's behavior for n = 2.

Answer 11

Because the definition is:
\[f\in O(g(x)) \iff \exists C,k \text{ such that }|f(x)| \le C|g(x)|, \forall x >k \]

Answer 12

In this case \(f(x) = 2n^2, g(x) = n^2\) And my C would be 2 and my k would be 0

Answer 13

Actually any x value can serve as the k witness.

Answer 14

Ack. that's terrible notation, sorry.

Answer 15

Should be f(n) and g(n) not f(x) etc.

Answer 16

Cool. Thanks!