Proving an equality

Question

Let $f(n) = n^ {\log n}$. Let $p(n)$ and $q(n) \geq n$ be polynomials. I want to show that for $n$ sufficiently large $f (n)$ satisfies $$p(n) < f (n) < 2^{q(n)}$$

starting from the above inequality doesn't yield any satisfying result.

Answer 1

Since $p(n)$ is a polynomial, $p(n) < c n^d$ where $d$ is the degree of $p$ and $c$ is the sum of the absolute value of its coefficients. So $p(n) < n^{d+1}$ for $n > c$. Therefore, if $\log n > d+1$, $p(n) < f(n)$.

For the upper bound, $f(n) = n^{\log n} = e^{\log^2 n} = 2^{(\log^2 n)/\log 2} $, so any polynomial $q$ such that $q(n) > (\log^2 n)/\log 2$ will work. Since $(\log^2 n)/n \to 0$ as $n \to \infty$, any polynomial will work.