Where exactly is $n\log n$ between $n$ and $n^2$?

Question

If I have $n^{1.161}$ and $n^{1.58}$, how do they compare in terms of time complexity relative to $n\log n$?

I only know that $n\log n$ is between $n$ and $n^2$.

I would probably factor out $n$ such that I will get $\log n$ vs $n^a$ where $0<a<1$, and that's as far I know.

Asymptotically, $n\log n$ is smaller than $n^\alpha$ if $\alpha > 1$ — Kitegi, Apr 11 '15 at 20:44

Hagen von Eitzen · Accepted Answer · 2015-04-11T20:43:48.540

5

As $n\to\infty$, $n\log n$ is between $n$ and $n^a$ for any $a>1$.

As you suggests, we can drop a factor of $n$ and simplify the above statement to: Given $\epsilon>0$. Then as $n\to\infty$, $\log n$ is between $1$ and $n^\epsilon $. The observation that $\log$ grows slower than any (positive) power is jut the reverse to the observation that the exponential function grows faster than any power.

edited Apr 11 '15 at 20:43

answered Apr 11 '15 at 20:37

Hagen von Eitzen

374,180

4

Why the downvotes? – Michael Biro Apr 11 '15 at 20:39
Ok but in the context of my question how would it compare? – maregor Apr 11 '15 at 20:42
@maregor As $1.58>1.161>1$, we have $n^{1.58}>n^{1.161}>n\log n$ (for $n$ sufficiently large). – Hagen von Eitzen Apr 11 '15 at 20:44

Where exactly is $n\log n$ between $n$ and $n^2$?

1 Answers1