# Heap Sort — Recurrence relation & Runtime analysis

`heap_sort(int Arr[]){    int heap_size = n;    build_maxheap(Arr);    for(int i = n; i >= 2 ; i--)    {        swap(Arr, 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, 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)