If $f(n) = (\sqrt{n})^{\sqrt{n}}$ and $g(n) = (\lg n)^n$, Is $f(n) = O(g(n))$ or $g(n) = O(f(n))$? 
If $f(n) = (\sqrt{n})^{\sqrt{n}}$ and $g(n) = (\lg n)^n$, is $f(n) = O(g(n))$ or $g(n) = O(f(n))$?

I think we have $g(n) = O(f(n))$ because no matter what, a polynomial function has to be grow quicker than logarithmic function, but I am not very strong when exponents come in. What do you think? Proof?
 A: The answer is $g$ grow faster.
We can take the ratio between the two and get:
$$\left(\frac{f(n)}{g(n)}\right)=\left(\frac{\sqrt n^\sqrt n}{\lg n^n}\right)=\left(\frac{n^{\sqrt n/2}}{\lg n^n}\right)=\left(\frac{n^{\frac12}}{\lg n^\sqrt n}\right)^\sqrt n$$
And this is clear that after some point(if $\lg$ is base 10 then after $24.13...$) we have $\frac{n^{\frac12}}{\lg n^\sqrt n}<1$ thus $f(n)=\mathcal O(g(n))$
The reason for this is that before the functions logarithmic or polynomial they are exponential, which is growing faster than both of the above, and in this exponential we have $g(n)$ grow exponentially faster than $f(n)$, so even if in $g$ we have $\log$ growing and in $f$ we have polynomial growing the log growing exponentially in compare to the polynomial and the polynomial growing linearly
A: In these cases, don't try to "guess." The exponents are confusing? Rewrite everything in the exponential form, then compare. Namely, 
$$\begin{align}
f(n) &= (\sqrt{n})^{\sqrt{n}} = e^{\sqrt{n} \log \sqrt{n}}= e^{\frac{1}{2}\sqrt{n} \log n} \\
g(n) &= (\log n)^n = e^{n \log \log n}
\end{align}$$
Now, you have to compare the exponents. Which one grows faster, $\sqrt{n} \log n$ or $n \log \log n$? It should be clear it's the latter, as
$$
\frac{\sqrt{n} \log n}{n \log \log n} = \frac{ \log n}{\sqrt{n}\log \log n} \xrightarrow[n\to\infty]{}0\,.
$$
Therefore, $\boxed{f(n) = O(g(n))}$. (Actually, we prove something stronger, specifically $f(n) = o(g(n))$).
