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!
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!