## anonymous 5 years ago 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 < http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-2-asymptotic-notation-recurrences-substitution-master-method/ > around minute 3. My calc background is extremely shaky, and I really don't understand what's going on there.

1. anonymous

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

2. anonymous

It is O(n^2)

3. anonymous

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

4. anonymous

Well

5. anonymous

Recall that big 0 is an upper bound

6. anonymous

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

7. anonymous

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

8. anonymous

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

9. anonymous

yeah he just made a mistake.

10. anonymous

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.

11. anonymous

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$

12. anonymous

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

13. anonymous

Actually any x value can serve as the k witness.

14. anonymous

Ack. that's terrible notation, sorry.

15. anonymous

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

16. anonymous

Cool. Thanks!