0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Many thanks dear @Steven for the great explanation!!!! $\endgroup$
    – learn9909
    Jul 19 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.