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?
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.