If I have two complicated logarithmic functions, say $\sqrt{\log n}$ and $\log(n(\log n)^3)$, and I have to compare them in terms of their asymptotic order. How do I do that? Do I have to create graphs, or is there another definitive way of doing that?
Asked
Active
Viewed 1,324 times
1 Answers
1
Using elementary properties of the logarithm we find out that $$\log(n \log^3 n) = \log n + 3\log\log n = O(\log n), $$ whereas $\sqrt{\log n} = o(\log n)$. So $\sqrt{\log n}$ grows more slowly.
Yuval Filmus
- 57,157
-
OK, got it just one more question,how do I compare log(n) and log(log n) then? – Parth Mody Sep 21 '12 at 00:56
-
From $\log n = o(n)$ it follows that $\log\log m = o(\log m)$ (substitute $n = \log m$). That $\log n = o(n)$ can be shown using l'Hopital's rule. – Yuval Filmus Sep 21 '12 at 02:11