14
$\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$
2
  • $\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, 2014 at 15:22
  • $\begingroup$ I've corrected your MathJax. $\endgroup$
    – J.G.
    Nov 20, 2019 at 13:38

5 Answers 5

16
$\begingroup$

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

$\endgroup$
7
$\begingroup$

Yes, There is a huge difference.

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

$\endgroup$
2
$\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)$.

$\endgroup$
2
  • $\begingroup$ You have to assume $n\ge3$ for $\log n\ge 1$. $\endgroup$ Dec 20, 2019 at 6:33
  • $\begingroup$ if n=1, logn = 0 isn't it? $\endgroup$ Jun 27, 2020 at 7:12
1
$\begingroup$

$$\lim_{n\to\infty}\frac{\log^2 n}{\log n} = \infty,$$

intuitively meaning that as $n\to\infty$, an $O(\log^2 n)$ time complexity algorithm takes infinitely times as much time as an $O(\log n)$ time complexity algorithm.

$\endgroup$
-2
$\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
$\endgroup$
2
  • 2
    $\begingroup$ I see what you mean, but when the OP asked which is "faster", I believe he was referring to which algorithm would be faster. Yes, log^2 n GROWS faster, but that means the algorithm is slower. Probably why you got downvoted a couple times. $\endgroup$
    – Ryan
    Apr 9, 2021 at 3:50
  • $\begingroup$ It means as input size, N grows, time complexity, log^2 N grows much faster than time complexity, log^2 N. So for large input size, N, the algorithm which has time complexity, log^2 N will be slower $\endgroup$
    – debaaryan
    Aug 13, 2022 at 5:31

You must log in to answer this question.

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