0
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

$$\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$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .