Basic growth of functions...Asymptotic notations question

• Mar 9th 2011, 06:01 PM
Nivg
Basic growth of functions...Asymptotic notations question
Hi all

http://i42.photobucket.com/albums/e316/K007/1c.gif

I'm probably missing something, it's not obvious that g(n) = O(f(n)) for all n (I don't see how 2^1000 boundaries of g(n) make any different here) ?
• Mar 9th 2011, 11:10 PM
CaptainBlack
Quote:

Originally Posted by Nivg
Hi all

http://i42.photobucket.com/albums/e316/K007/1c.gif

I'm probably missing something, it's not obvious that g(n) = O(f(n)) for all n (I don't see how 2^1000 boundaries of g(n) make any different here) ?

Yes, \$\displaystyle g(n)=O(f(n))\$, but is that what the question is asking for? The wording seems pretty obscure.

Could it want something like: \$\displaystyle f(n)=O(n^3\log(n))\$ and \$\displaystyle g(n)=O(n^3)\$ and so \$\displaystyle g(n)=O(n^3\log(n))\$.

Also you probably are expected to justify \$\displaystyle f(n)=O(n^3\log(n))\$

CB
• Mar 10th 2011, 11:14 AM
Nivg
ok thanks didn't think it through.