0
$\begingroup$

Proving $\log^n(n)=\omega(n^{\log(n)}) $

Hey everyone. I am trying to prove that $\displaystyle\lim_{n\to\infty}\frac{(\log n)^n}{n^{\log n}}=\infty $

(here $\log n= \log_2 n$)

I've tried proving this using squeeze theorem, since using L'Hôpital's rule in this case is quite out of question. I thought of proving this using the definition: $\log^n(n)=\omega(n^{\log(n)}) \iff \forall C>0 \ \ \exists N>0$ s.t. $ \forall n\ge N , (\log n)^n \ge C \cdot n^{\log n} $

Let $C$ be some arbitrary positive value. Then we can say that for all $n \ge 2^C \implies (\log n)^n>C^{2^C} $

and $ n^{\log n} \ge 2^{C^2} $

If $C>2$ then $C^{2^C} \ge 2^{C^2} $ (How can I elegantly prove this?) $\implies (\log n)^n \ge n^{\log(n)} \ , \ \forall n\ge 2^C$

Else, $0\lt C \lt 2 $... I'm quite lost and not sure if this direction is alright. I would love to hear your thoughts. Thank you :)

$\endgroup$
1
$\begingroup$

Let $g(n)=\frac {(\log n)^n}{n^{\log n}}.$

Then $$\log g(n)=n(\log n)-(\log n)(\log n)=(n-\log n)(\log n).$$

As long as your $\log$ is to a base $B>1$, we have $n-\log n\to \infty$ and $\log n \to \infty$ so $\log g(n) \to \infty$ so $g(n)\to \infty.$

$\endgroup$
1
$\begingroup$

Hint: Using $a^b = 2^{b \log_2 {a}}$, we see that $(\log_2 n)^n = 2^{n\log_2 n}$ and $n^{\log_2 n} = 2^{(\log_2 n)^2}$. Hence the ratio you are interested in is equal to $$2^{n\log_2 n - (\log_2 n)^2} = 2^{(\log_2{n}) (n - \log_2 n)}.$$ Can you explain why this tends to $\infty$ as $n\to \infty$?

$\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.