# How to prove that $n^{1.1} \not\in O(n(\log n)^2)$

This is a problem from a university exam:

True or false: $n^{1.1} \in O(n(\log n)^2)$.

The solution says False, but I'm unable to prove it. I tried using the limit test for Big-O:

$\lim_{n \to \infty} \frac{T(n)}{f(n)} = \lim_{n \to \infty} \frac{n^{1.1}}{n(\log n)^2} = \lim_{n \to \infty} \frac{n^{0.1}}{(\log n)^2}$

EDIT: Wolfram Alpha says that this limit is $\infty$, which is not a constant as the limit test requires. But I still don't know how to compute this limit by hand.

• And what did you find for the last limit?
– Did
Aug 16, 2014 at 20:47
• I couldn't find a way to proceed for that limit. Aug 16, 2014 at 20:47

$$\frac{k}{\log k}\to\infty\implies\frac{n^{0.1}}{(\log n)^2}=\frac1{400}\cdot\left(\frac{n^{0.0.5}}{\log(n^{0.05})}\right)^2\to\infty$$
More basic looking, by L'Hopital $$\lim_{x \rightarrow \infty} \frac{x}{\log x} = \infty$$
Next $$\lim_{x \rightarrow \infty} \frac{x}{(\log x)^2 } =\lim_{x \rightarrow \infty} \frac{x}{2 \log x } = \infty$$
The general induction step is $$\lim_{x \rightarrow \infty} \frac{x}{(\log x)^k } =\lim_{x \rightarrow \infty} \frac{x}{k (\log x)^{k-1} } = \infty$$
For non-integer exponents comparison may be used. Anyway, your $$\left( \frac{n^{0.1}}{(\log n)^2} \right)^{10} = \frac{n}{(\log n)^{20}}$$ and both go to infinity.