# 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 '14 at 15:22
• – J.G. Nov 20 '19 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$. – Alberto Saracco Dec 20 '19 at 6:33

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