Proving with Big-O notation
Posted on 2011-02-26
I was just thinking about Big-O notation... I was trying to prove n^2 = O(2^n).
This is a homework problem... so I don't expect a straight answer... but maybe a nudge in the right direction? =)
I never quite understood how Big-O worked... after dealing with math that had to be exact and precise... its kinda hard for me to wrap my head around this "almost" idea.
My initial thought about proving this statement was to say that the graphs of these two functions would behave in a similar way... but the gap between these two functions keeps increasing... (When n = 10; n^2 = 100 and 2^10 = 1024).
Then I thought that they might have similar slopes... and that's why they were equal, but their slopes were nowhere near each other...
The only thing I can see after re-reading the chapter was that both sides grew exponentially, and that's why they'r equal.
Am I on the right track?
Appreciate any help on this!