Why does $(\log n)^{\log n} = \Omega(n^{10})$?

Question

In other words, show that $(\log n)^{\log n} \ge c\cdot n^{10})$ for some constant $c>0$.

I'm not sure how to prove it, how can I write $(\log n)^{\log n}$ in a simpler way?

Are we using Big Omega notation? And if so, which? https://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation — Simply Beautiful Art, Sep 18 '16 at 13:07
Shouldn't it be $(\log(n))^{\log(n)}\leq Cn^{10}$? The inequality you've written is clearly false. — Olivier Moschetta, Sep 18 '16 at 13:09

score 2 · Accepted Answer · answered Sep 18 '16 at 13:08

2

Hint: take logarithm of both sides

answered Sep 18 '16 at 13:08

PSPACEhard

10,283

Thank you, I did and got to: $lognlog(logn) \gt 10logn$? – Ilan Aizelman WS Sep 18 '16 at 13:09
@IlanAizelmanWS $\log \log n > 10$ for sufficiently large $n$. – PSPACEhard Sep 18 '16 at 13:10
@IlanAizelmanWS Yes, then divide both side by $\log n$ for clarity. – Simply Beautiful Art Sep 18 '16 at 13:10

Robert Z · Answer 2 · 2016-09-18T13:11:56.693

2

Note that $$(\log n)^{\log n}=\exp(\log n\cdot \log(\log(n)))=n^{\log(\log(n))}$$ Hence $(\log n)^{\log n} = \Omega(n^{a})$ for any $a>0$ because $\log(\log(n))$ goes to infinity and it is therefore bigger than any constant.

edited Sep 18 '16 at 13:11

answered Sep 18 '16 at 13:10

Robert Z

145,942

Why does $(\log n)^{\log n} = \Omega(n^{10})$?

2 Answers2