I was given homework to sort some (14) functions in order of their growth rate. I am confused about two functions $3^\sqrt{\log n}$ and $n^{\log n}$: about where these two lie within those 14 functions.
I tried wolframalpha but it does not plot the graphs well and is not very useful. Which technique I should use to compare growth rates of functions?
EDIT:
I tried taking logs, but it also confused at places. For example I have taken double logs below
log(5) + log(log(n)) AND log(log(5n+20))
I don't know which one is bigger here
Best Answer
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. $$