4

Find $k$ such that

$$(\lg n)^{\lg n}= \Theta (n^k), k \geq 2$$

That's what I did so far:

$$(\lg n)^{\lg n}=\Theta(n^k) \text{ means that } \exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ c_1 n^k \leq (\lg n)^{\lg n} \leq c_2n^k$$

How can I continue?

Thomas Andrews
  • 177,126
evinda
  • 7,823
  • $(\log n)^{\log n} = e^{\log n\log\log n} = n^{\log\log n}$. Since $\log\log n$ is unbounded, I don't think you'll be able to solve this, because it isn't true for any $k$... – Thomas Andrews Aug 09 '14 at 16:23
  • So,we can't neither find an $O$,right? But we could find an $\Omega$,or not? – evinda Aug 09 '14 at 16:24
  • You can't find a polynomial $O$, no. Wikipedia gives two definitions for $\Omega.$ – Thomas Andrews Aug 09 '14 at 16:27
  • With $\Omega$ I mean that the first inequality of the definition above stands:

    $$\exists c>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: \ cn^k \leq (\lg n)^{\lg n}$$

     – evinda Aug 09 '14 at 16:30

1 Answers1

0

I find that $\ln n$ is a gross exponent, and so I want to simplify the expression. You're right when you say we want to find conditions so that

$$ c_1 n^k < \ln n ^{\ln n} < c_2 n^k,$$

but if we take logs everywhere, then this is the same as finding conditions so that

$$\ln c_1 + k \ln n < \ln n (\ln \ln n) < \ln c_2 + k \ln n.$$

Now we run into a problem. For any finite $k$, eventually $\ln \ln n$ is going to grow much bigger than $k$. Arbitrarily bigger, even. So we will never find conditions so that $\ln n (\ln \ln n) < \ln c_2 + k \ln n$. We are forced to conclude that $(\ln n) ^ {\ln n}$ is not $\Theta (n^k)$ for any $k$.

More interestingly, even though logs are small, exponential growth is huge. However, since it won't win until $\ln \ln n \gg k$, it will take a really, really long time for $(\ln n) ^ {\ln n}$ to catch up to the initial polynomial growth.

davidlowryduda
  • 91,687