Heap Sort — Recurrence relation & Runtime analysis

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)

Alternatively

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 ^(0+1) * log n) = O(n * log n)