The book CLRS says that any comparision sort algorithm requires omega(nlgn) comparisions n the worst case. My question is that why for heapsort it's O(nlgn) not omega(nlgn) since heapsort is also a comparision based algorithm?
1 Answer
$\begingroup$
$\endgroup$
1
Comparison based sorting algorithms require $\Omega(n \log n)$ comparison (notice the big omega).
Heapsort uses $O(n \log n)$ comparisons. This is not a contradiction since $\Omega(n \log n) \cap O(n \log n) \neq \emptyset$, i.e., there are functions of $n$ that are both in $\Omega(n \log n)$ and in $O(n \log n)$.
To be more precise, all comparison-based algorithms must use $$ \log_2 n! \ge \log_2(n^n e^{-n}) = n\log n - n \log_2 e $$ comparisons, while Heapsort uses at least $n \log n - n \log_2 e$ comparisons (since it is a comparison-based sorting algorithm) and at most $c n \log n$ comparisons for some fixed constant $c>0$.
-
$\begingroup$ Many thanks dear @Steven for the great explanation!!!! $\endgroup$learn9909– learn99092021-07-19 15:03:31 +00:00Commented Jul 19, 2021 at 15:03