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?
[Math] Comparing asymptotic order of logarithmic functions
asymptotics
Related Solutions
You could just compare the two functions. The base 3 is constant and the base $n$ tends to infinity. Now compare the exponents: $\sqrt{\log n}$ grows more slowly than $\log n$. These two observations imply that $3^{\sqrt{\log n}}$ grows more slowly that $n^{\log n}$.
In fact, for $n>10$: $$ { n^{\log n}\over3^{\sqrt{\log n}}}\ge { 10^{\log n}\over3^{\sqrt{\log n}}} \ge{ 10^{\log n}\over3^{ \log n }}={(10/3)^{\log n}}\rightarrow\infty. $$
Using a bit of algebraic manipulation I get: $$4^{\sqrt{n}} = (2^2)^{\sqrt{n}} = 2^{2 \sqrt{n}}$$
I think this makes it much easier to compare the functions. Intuitively the numerator in the first function overpowers the denominator (exponential vs subexponential), so we can think of it as just $2^n$ (for sufficiently large $n$, as in the Big O sense). $2 \sqrt{n}$ is much less than n for large n thus we conclude the first function grows faster than the second.
Normally when comparing functions asymptotically, the sufficiently large n could actually be quite large. In this case though, it is low. If you plug your equations and $2^n$ into Wolfram Alpha:
the plot shows $n \approx 10$ is the sufficiently large n. Notice in the plot how $2^n$ and your first function are almost the same with your's just slightly to the right. In fact, if you plotted the graph from $1$ to $20$, the second equation barely shows up.
Best Answer
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.