Simple and friendly time and space complexity analysis for Heapsort

Question

I was not able to find a simple and friendly time or space complexity analysis for Heapsort. This is not a duplicate question on stackoveflow.

Worst Time complexity let's get only this example, for heapsort it is O(n log(n)). How do we easily compute it?

Let's compare with the mergesort algorithm.

Mergesort

void mergeSort(int arr[], int l, int r)    // T(n), n being the number of elements in arr
{ 
    if (l < r) 
    { 
        ........ // constant operations

        mergeSort(arr, l, m);     // T(n/2) since we apply it on aprox half
        mergeSort(arr, m+1, r);   // T(n/2) since we apply it on aprox half

        merge(arr, l, m, r);    // c*n , out of scope to analyse merge() 
    } 
}

The purpose is to analyse the complexity, not the algorithm itself: https://www.geeksforgeeks.org/merge-sort/

Therefore, if n is the array's number of elements and c is a const, we have:

T(n) = c, if n=1
T(n) = 2*T(n/2) + c*n, if n>1
so we can rewrite
T(n) = 2*( 2*T(n/4) + c*n/2 ) +c*n
T(n) = 4*T(n/4) + 2cn
T(n) = 4*( 2T(n/8) + c*n/4 ) + 2cn
T(n) = 8*T(n/8) + 3c
...
T(n) = 2^k * T(n/2^k) + kcn
if we use T(1) that we know => 1 = n/2^k => k = log(n) =>
T(n) = 2^(log(n)) * T(1) + nlog(n)
T(n) = n + nlog(n)
=> nlog(n)

Full explanation: https://www.youtube.com/watch?v=0nlPxaC2lTw&list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U&index=6

Now, let's get the example of heapsort.

I mention I already checked on stackoverflow, but there is no clear answer: Analysis of speed and memory for heapsort or heapsort - implementation's complexity

Heapsort

The purpose is to analyse the complexity, not the algorithm itself: https://www.geeksforgeeks.org/heap-sort/

// main function to do heap sort 
void heapSort(int arr[], int n) 
{ 
    // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i);                       // n/2 * TH(n)

    // One by one extract an element from heap 
    for (int i=n-1; i>0; i--) 
    { 
        // Move current root to end 
        swap(arr[0], arr[i]); 

        // call max heapify on the reduced heap 
        heapify(arr, i, 0);              // (n-1) * TH(i)
    } 
} 

T(n) = c, if n=1
TH is the time complexity for heapify()
T(n) = n/2 * TH(n) + (n-1) * TH(i) , where i is decreasing from n-1 to 1

The problem is how to calculate TH(n) = log(n). Because based on it, T(n) = n*log(n)

Therefore, the code for heapify for which we need to compute TH(n):

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest);       //  how to express TH in terms of n ?
    } 
}

TH(n) = c, if n=1
worst case when the largest if never root:
TH(n) = c + ? * TH( ? )

how to write the recursive expression?

There is also the logical deduction, but let's avoid this strategy:

There are log(n) levels. 
Half of the elements will be on the last layer, not touched by heapify().
So log(n) elements are touched. 
This might be a good strategy, but not simple or friendly enough.

Space complexity

How to compute O(1) as space complexity, since we use a heap of n elements? Or maybe the O(1) value is wrong : reference https://www.bigocheatsheet.com/ .

The height of a complete binary tree containing n elements is log(n) To fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it. In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps. During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log(n) ~ nlogn. — kaileena, Jun 06 '20 at 20:36

Simple and friendly time and space complexity analysis for Heapsort

0 Answers0