0

Show that $(\log n)^{\log n}\in\Omega (n)$

Proceeding with a common logarithm property, we get $$(\log n)^{\log n}=(n^{\log\log n})$$

How do I deduce that $$(n^{\log\log n})\in\Omega(n)$$

If I say that $n=b^{b}$ where $b$ is the base of the logarithm then it can be true, but doesn't it defeat the purpose of it being linear?

Here, $\Omega,\Theta,\mathcal{O}$ are the well known asymptotics, i.e. lower bound, upper bound and the big O.

This was found in MIT 6.006 Spring 2020, question number 6 although they assumed a base $2$ logarithm.

Anindya Prithvi
  • 1,194

1 Answers1

1

When $n$ is sufficiently large, $\log \log n \geq 1$. Therefore $n^{\log \log n} \geq n^1 = n$ for $n$ sufficiently large.

Adam
  • 2,677