0
$\begingroup$

It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ?
The argument here is, If my input has all the same keys, then every time I delete the root, I do not need to heapify, I just need to swap with the rightmost leaf.

Why is the above argument not valid ?

$\endgroup$
1
$\begingroup$

Big O is for measuring the worst case time complexity, and in this case it is $O(n)$. The best case is written as $\Omega$. Here is a paper describing the reasoning for the best case. We generally do not consider the case of having only identical elements in the list.

$\endgroup$
  • $\begingroup$ Actually, both $O$ and $\Omega$ can be applied to various functions that can represent the number of steps an algorithm takes on an input of size $n$, or something completely different. That is, the notation itself has nothing do with "worst" or "best" case, or even algorithm analysis per se. $\endgroup$ – Juho Feb 2 '17 at 20:33
  • $\begingroup$ Well strictly they are about the asymptotic bounds of functions that apply to any two functions, we just use them in a specific way in comp sci. $\Omega$ is the lower bound, i.e our function must be asymptotically greater then this, so we translate that to be "in the best case our algorithm must take longer than this". $\endgroup$ – lPlant Feb 2 '17 at 20:39
  • $\begingroup$ @lPlant No, we don't do that. Worst cases are usually associated with $\mathcal{O}$ bounds simply because it's easier to prove upper than lower bounds, therefore they are more likely to appear when one studies computer science. Statements such as "the best case of heapsort is $\mathcal{O}(n^{50})$" or "the worst case of heapsort is $\Omega(1)$" are maybe not very insightful, but both correct and consistent with usual notation. $\endgroup$ – quicksort Feb 2 '17 at 21:02
1
$\begingroup$

Because the analysis is performed assuming that there is a strict total order on the keys. Therefore if you are sorting, for example, integers on their usual order, the lower bound applies only as long as each key is different. If you allow the order to not be strict then the analysis is not particularly interesting, your example is indeed a best case.

Observe that the assumption of a strict total order is actually a small cheat, because we are also implicitly assuming that all comparisons cost $\Theta(1)$. If we disallow repeated keys, then the number of different keys is not bound by a constant, which means that the key size is also not bound by a constant, in contradiction with the constant cost assumption for comparisons.

$\endgroup$

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.