0
$\begingroup$

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.

$\endgroup$
1
  • 2
    $\begingroup$ Please don't delete your question after you've received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to the person who asked but also to others in the future. Deleting the question can be considered impolite to the answerer who spent time to write out an answer, with this understanding in mind. Thank you for your understanding. $\endgroup$ – D.W. May 24 at 3:08
4
$\begingroup$

Here is a way to show it without limits. Let $n = 2^x$. Now you are comparing the growth rates of $2^x$ and $x^x$.

$\endgroup$
1
$\begingroup$

$$ \lim_{n \to \infty} \frac{(\log n)^{\log n}}{n} = \lim_{n \to \infty} \frac{2^{\log ( (\log n)^{\log n})}}{n} = \lim_{n \to \infty} \frac{2^{(\log n) \cdot \log \log n}}{n} = \lim_{n \to \infty} \frac{n^{\log \log n}}{n} = \lim_{n \to \infty} n^{\log \log n -1} = +\infty. $$

$\endgroup$
4
  • $\begingroup$ yes thank you! i did try it with limits but is there any way to show it without using limits? $\endgroup$ – ediblebanana May 23 at 23:33
  • $\begingroup$ For $n \ge 2^{2^k}$ you have $(\log n)^{\log n} = n^{\log \log n} \ge n^k$ . This shows that $(\log n)^{\log n} = \Omega(n^k)$ for any constant $k$. If you only care about showing that $(\log n)^{\log n} = \omega(n)$ you can pick, e.g., $k=2$. $\endgroup$ – Steven May 23 at 23:36
  • $\begingroup$ That's precisely what I wanted to show yes, I however haven't really brushed up on my logarithms which is probably why this was harder for me to show, how exactly do we go from $(\log{n})^{\log{n}} = n ^{\log{\log{n}}}$? $\endgroup$ – ediblebanana May 23 at 23:52
  • 1
    $\begingroup$ Using exactly the same steps in my answer. The properties I'm using are $x = 2^{\log x}$, $\log x^y = y \log x$ , and $2^{xy} = (2^x)^y$. The base of all logarithms is $2$. $\endgroup$ – Steven May 23 at 23:55

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.