I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we want to sort).

Since inserting n items to a heap takes O(n) , and each delete-min takes O(d log n/ log d), I was thinking the bound is O(n d log n / log d). Am I right? If so, how do I prove that it is indeed a tight bound?


  • 2
    $\begingroup$ What have you tried? Where did you get that from? What attempts at proving it have you made? Have you read our reference questions, e.g., cs.stackexchange.com/q/23593/755? We want to help you understand concepts, not do your exercise for you. $\endgroup$ – D.W. Jun 14 '15 at 23:12
  • 1
    $\begingroup$ Related: A d-ary heap problem from CLRS $\endgroup$ – hengxin Jun 15 '15 at 6:52
  • $\begingroup$ Note that $O(d \log n / \log d) = O(\log n)$, as everything else is constant (independent of $n$). $\endgroup$ – vonbrand Nov 12 '15 at 9:39

Inserting $n$ items to a heap takes $\Theta(n)$.

You probably mean that "building" a heap takes $\Theta(n)$.

Each delete-min takes $\Theta(d \lg n/ \lg d)$, I was thinking the bound is $\Theta(n d \lg n / \lg d)$.

I agree with you.

How do I prove that it is indeed a tight bound?

How tight do you want to prove it is? Do you want to show that the worst-case running time of $d$-ary heap-sort is $\Omega(n d \lg n / \lg d)$? If so, I tend to think it is indeed tight.

For a hint, this paper: The Analysis of Heapsort mentions that (in Abstract)

The number of keys moved during $2$-ary heap-sort when sorting a random file of $n$ distinct elements is $n \lg n + O(n)$ in the worst case.

It even further proves that (Notice that it is for the best case)

Theorem 1 (Page 7): Heap-sort ($2$-ary) requires at least $\frac{1}{2} n \lg n- O(n)$ data moves for any heap composed of distinct keys.

Maybe you can adapt it to $d$-ary heap-sort.

| cite | improve this answer | |

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.