1
$\begingroup$

How do I convert ${\log n}^n$ to the form $n^x$, for some $x$? I'd like to compare the big-O runtime of $(\log n)^n$ to $n^{\log n}$ directly. Intuitively, $(\log n)^n$ grows faster since the exponent grows faster but I'm not sure how to prove the result directly. Any tips or guidance is appreciated.

$\endgroup$
1
  • $\begingroup$ Take $\log$ of both sides to get $x=\frac{n\log\log n}{\log n}$. $\endgroup$
    – A.S.
    Feb 23 '16 at 17:18
4
$\begingroup$

Well, you want to write

$$(\log n)^n = n^x$$

If you take logarithm of both sides:

\begin{align*} \log \left( \log n \right)^n &= \log(n^x) \\ n \log(\log n) &= x \log n \\ x &=\frac{n \log (\log n)}{\log n}\end{align*}

$\endgroup$
4
  • $\begingroup$ Glad it helped. $\endgroup$
    – mweiss
    Feb 23 '16 at 17:27
  • 1
    $\begingroup$ Thank you @wythagoras for correcting the important omission of $n$ in the numerator. $\endgroup$
    – mweiss
    Feb 23 '16 at 18:07
  • $\begingroup$ Please thank @Simpson17866 instead. I merely approved and improved his edit by fixing a little formatting. $\endgroup$
    – wythagoras
    Feb 23 '16 at 18:16
  • $\begingroup$ Glad I could help :) $\endgroup$ Feb 23 '16 at 20:18
2
$\begingroup$

How about this $(\ln n)^n = e^{n\ln\ln n}$ and $n^{\ln n} = e^{\ln n\ln n}$. Is it helpful?

$\endgroup$
2
  • $\begingroup$ Maybe easier to parse: $e^{n (\log\log n)}$ vs. $e^{(\log n)^2}$. $\endgroup$
    – Clement C.
    Feb 23 '16 at 17:16
  • $\begingroup$ I need the answer to have base $n$. $\endgroup$ Feb 23 '16 at 17:17
1
$\begingroup$

We can rewrite it as following:

$$\log(n)^n = (n^{\log_n (\log (n))})^n = n^{n \log_n( \log(n))} = n^{\frac{n \log (\log (n))}{\log(n)}}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.