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$ 25 Answers
$\begingroup$$(\log(n))^2$ means $\log^2(n)$
$\endgroup$ $\begingroup$Yes, There is a huge difference.
If$$x=\log n$$ Then$$x^2=\log^2n$$
$\endgroup$ $\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$$$\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$ $\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
