# 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

- If a<1 then T(n) = O(n^k)
- If a=1 then T(n) = O(n^k+1)
- 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)