CODEWITHSUNDEEP
c++algorithmbig-otime-complexityheapsort
David Velasquez
David Velasquez

Reputation: 2366

Is my heap sort algorithm time complexity analysis correct?

Here is the algorithm:

void heapSort(int * arr, int startIndex, int endIndex)
{
    minHeap<int> h(endIndex + 1);

    for (int i = 0; i < endIndex + 1; i++)
        h.insert(arr[i]);

    for (int i = 0; i < endIndex + 1; i++)
        arr[i] = h.deleteAndReturnMin();
}

The methods insert() and deleteAndReturnMin() are both O(log n). endIndex + 1 can be referred to as n number of elements. So given that information, am I correct in saying the first and the second loop are both O(n log n) and thus the time complexity for the whole algorithm is O(n log n)? And to be more precise, would the total time complexity be O(2(n log n)) (not including the initializations)? I'm learning about big O notation and time complexity so I just want to make sure I'm understanding it correctly.

Upvotes: 0

Views: 593

Answers (1)

Strikeskids
Strikeskids

Reputation: 4052

Your analysis is correct.

Given that the two methods you have provided are logarithmic time, your entire runtime is logarithmic time iterated over n elements O(n log n) total. You should also realize that Big-O notation ignores constant factors, so the factor of 2 is meaningless.

Note that there is a bug in your code. The inputs seem to suggest that the array starts from startIndex, but startIndex is completely ignored in the implementation.

You can fix this by changing the size of the heap to endIndex + 1 - startIndex and looping from int i = startIndex.

Upvotes: 3

Related Questions