big O with different orders

Question

I'm trying to show the following and I'm not quite sure how:

$f_1(n) = n^n$ is $O(f_2(n) = 3^{2^n})$ and $f_2(n) = 3^{2^n} = O(f_3(n) = 2^{3^n}) $

does anyone have an idea? calculating the limits is an option it's just that I don't get too far that way either. thanks ahead.

score 0 · Accepted Answer · answered Mar 29 '19 at 01:51

0

For the first, it is enough to show that $\dfrac{n^n}{2^{3^n}} \lt c$ for some $c > 0$ for all large enough $n$. Since $\dfrac{n^n}{2^{3^n}} \to 0$, this is more than enough.

For the second, when there are complicated exponents, I take logs. This makes $f_2(n) = 3^{2^n} = O(f_3(n) = 2^{3^n}) $ become $\ln f_2(n) =2^n \ln 3 $ and $\ln f_3(n) =3^n \ln 2 $ and clearly $\ln f_3(n) $ is a lot larger.

answered Mar 29 '19 at 01:51

marty cohen

107,799

How can you show the first limit? – giorgioh Mar 29 '19 at 01:54
Take logs. Note that if $\ln f(n)/\ln g(n) \to 0$ and $f(n), g(n) \to \infty$ then $f(n)/g(n) \to 0$. – marty cohen Mar 29 '19 at 02:02
Thanks for your help – giorgioh Mar 29 '19 at 10:29

big O with different orders

1 Answers1