What is Heap Sort's recurrence relation?

Question

I need to calculate Heap Sort's time complexity using Master's Theorem, but I don't know which is the recurrence relation. I know that it's complexity is O(n log n), since it traverses n times a binary tree. But I need to specifically use Master's Theorem, for which I need the recurrence relation. Which is the relation for Heap Sort?

Answer 1

Let us start with the heapsort algorithm:

heap_sort(int Arr[])
{
    int heap_size = n;

    build_maxheap(Arr);
    for(int i = n; i >= 2 ; i--)
    {
        swap(Arr[1], Arr[i]);
        heap_size = heap_size - 1;
        heapify(Arr, 1, heap_size);
    }
}

The build_maxheap() funnction has a standard implementation of O(n).

The important part of the sorting is the for loop, which executes for n times. Inside that we have a swap method call and heapify method call. The heapify method is a standard walk through of complete binary tree. Hence, the complexity is O(log n)

T(n) = O(n) + n * O(log n) = O(n * log n)

Master theorem is useful for solving recurrence relations of many divide and conquer algorithms.

Now, if you are interested in application of master theorem. We can implement a recursive algorithm

heap_sort(int Arr[])
{
    int heap_size = n;
    build_maxheap(Arr);

    heap_sort_recurse(Arr, heap_size);

}

heap_sort_recurse(int Arr[], heap_size)
{
    swap(Arr[1], Arr[n]);
    heap_size = heap_size - 1;
    heapify(Arr, 1, heap_size);
}

In this case you may have a recurrence equation as below

T(n) = T(n-1) + O(log n)

Clearly, this cannot be solved directly by master theorem. There is a modified formula derived for Subtract-and-Conquer type.

This link might be useful.

For recurrences of form,

T(n) = aT(n-b) + f(n)

where n > 1, a>0, b>0

If f(n) is O(n^k) and k>=0, then

1. If a<1 then T(n) = O(n^k)
2. If a=1 then T(n) = O(n^k+1)
3. if a>1 then T(n) = O(n^k * a^n/b)

Applying this,

We have a = 1, b = 1, k = 0

Therefore, 2nd case is applicable. Hence,

T(n) = O(n⁰⁺¹ * log n) = O(n * log n)

Hope it helps!