# Difference between $\log n$ and $\log^2 n$

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. )

• Note that $log^2(n)\ne log_2(n) = ld(n)$, which also occurs often in complexity analyses, particularly of binary data structures.
– user139000
Oct 26, 2014 at 15:22
• – J.G.
Nov 20, 2019 at 13:38

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

Yes, There is a huge difference.

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

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)$.

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

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

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

• 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.
– Ryan
Apr 9, 2021 at 3:50
• 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 Aug 13, 2022 at 5:31