Convert $(\log n)^n$ to the form $n^x$ for some $x$

Question

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.

Take $\log$ of both sides to get $x=\frac{n\log\log n}{\log n}$. — A.S., Feb 23 '16 at 17:18

mweiss · Accepted Answer · 2016-02-23T18:17:27.880

4

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*}

edited Feb 23 '16 at 18:17

answered Feb 23 '16 at 17:16

mweiss

23,647

Glad it helped. – mweiss Feb 23 '16 at 17:27
1

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

score 2 · Answer 2 · answered Feb 23 '16 at 17:12

2

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

answered Feb 23 '16 at 17:12

echzhen

1,029

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

score 1 · Answer 3 · answered Feb 23 '16 at 17:14

1

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)}}$$

answered Feb 23 '16 at 17:14

wythagoras

25,026

Convert $(\log n)^n$ to the form $n^x$ for some $x$

3 Answers3