5
$\begingroup$

I'm researching the different execution time of various sorting algorithms and I've come across two with similar times, but I'm not sure if they are the same.

Is there a difference between $\log n$ and $\log^2 n$?

EDIT:

Follow up question: in terms of complexity , which would be faster, $O(\log n)$ or $O(\log^2 n)$? My guess would be the first one. (Note, this is not homework, I'm just trying to understand the difference between quicksort and bitonic sort on a hypercube topology. )

$\endgroup$
  • $\begingroup$ Note that $log^2(n)\ne log_2(n) = ld(n)$, which also occurs often in complexity analyses, particularly of binary data structures. $\endgroup$ – user139000 Oct 26 '14 at 15:22
  • $\begingroup$ I've corrected your MathJax. $\endgroup$ – J.G. Nov 20 '19 at 13:38
7
$\begingroup$

$(\log(n))^2$ means $\log^2(n)$

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

Yes, There is a huge difference.

If$$x=\log n$$ Then$$x^2=\log^2n$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Regarding your follow up question: If we assume $n \geq 1$, we have $\log n \geq 1$.
With that we have $\log^2n =\log n * \log n \geq \log n$ (since $\log n \geq 1$).

So yes in Terms of complexity $\mathcal{O}(\log{}n)$ is faster than $\mathcal{O}(\log^2n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You have to assume $n\ge3$ for $\log n\ge 1$. $\endgroup$ – Alberto Saracco Dec 20 '19 at 6:33
-1
$\begingroup$

O(log^2 N) is faster than O(log N) because of

O(log^2 N) = O(log N)^2

           = O(log N * log N)

Therefore Complexity of O(log^2 N) > O(log N).

Just take n as 2, 4, 16;

          O(log^2 N)         O(log N)

2  -->     1^2 = 1               1
4  -->     2^2 = 4               2
16 -->     4^2 = 16              4
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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