How would you prove n^100 is O(2^n)
Favorites|Homepage
Subscriptions | sitemap
HOME > > How would you prove n^100 is O(2^n)

How would you prove n^100 is O(2^n)

[From: ] [author: ] [Date: 12-12-23] [Hit: ]
= lim(n→∞) (2^n * (ln 2)^100) / 100!= ∞.This implies that, in particular, 2^n / n^100 > 1 for sufficiently large n.Hence,......
please, help me with this big-O exercise

-
Using L'Hopital's Rule, we have
lim(n→∞) 2^n/n^100
= lim(n→∞) (2^n * ln 2) / (100n^99)
= lim(n→∞) (2^n * (ln 2)^2) / (100 * 99n^98)
...
= lim(n→∞) (2^n * (ln 2)^100) / 100!
= ∞.

This implies that, in particular, 2^n / n^100 > 1 for sufficiently large n.
==> n^100 < 1 * 2^n for sufficiently large n.

Hence, n^100 is O(2^n).

I hope this helps!
1
keywords: would,you,How,is,100,prove,How would you prove n^100 is O(2^n)
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .