I am trying to rank $\log n $, $\log_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise.

The answer I have is $\log_{10} n $, $\log n $, $\sqrt{n}$, $n^{0.8}$, $n \log n$, $n \log n^2$,

Is this right? And possibly explain the reason behind it? thank you!

  • 4
    $\begingroup$ You should probably also mention which ones have the same order. $\;$ $\endgroup$
    – user12859
    Dec 10 '14 at 2:52
  • 2
    $\begingroup$ Also say where you are unsure and why you are unsure. $\endgroup$
    – usul
    Dec 10 '14 at 4:03
  • $\begingroup$ Have a look here. As a short answer, though, it depends on the size of n $\endgroup$
    – jbutler483
    Dec 10 '14 at 9:09
  • 1
    $\begingroup$ You should say "in increasing asymptotic growth", rather than "in increasing asymptotic complexity". since the functions are independent of the use they may have in complexity analysis. Regarding complexity, it is quite clear the $\log n$ has a greater complexity than $n^2$ since it is much easier to compute a square than a $\log$. It is a matter of not confusing what the function are, and what they are used for. Precision is important in mathematical language. $\endgroup$
    – babou
    Dec 10 '14 at 9:54
  • $\begingroup$ How does $\log_{10}(n)$ relate to $\log(n)$, precisely ? What about $\log (n^{25})$ ? $\endgroup$
    – babou
    Dec 10 '14 at 10:04

The answer is correct. Let's verify it

$\log_{10}n $ and $\log{n}$ belong to the complexity class $O(\log{n})$, because they differ by a constant factor, hence $\log_{10}n \asymp \log{n}$.

$n^{0.8} \succ \sqrt{n}$, because $0.8 > \frac{1}{2}$. The last pair $n\log{n}$ and $n\log{n}^2$ belong to the complexity class $O(n\log{n})$ because they also differ by a constant factor ($n\log{n^2} = 2n\log{n}$), hence $n\log{n} \asymp n\log{n^2}$. Finally we'll show that $\sqrt{n} \succ \log{n}$ and $n\log{n} \succ n^{0.8}$. The last one is obvious and I'll leave to you to prove that $\sqrt{n} \succ \log{n}$ (I claim that is true, if you face problems with it I'll expand the answer with proof).


Not the answer you're looking for? Browse other questions tagged or ask your own question.