Analysis of Algorithm

Time Complexity of building a heap

Time Complexity of building a heap
Time Complexity of building a heap - Analysis of Algorithm - Consider the following algorithm for building a Heap of an input array A.What is the worst case

Consider the following algorithm for Time Complexity of building a heap of an input array A.

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

What is the worst case time complexity of the above algo?
Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n). See following links for the proof of time complexity.

READ  Stability in sorting algorithms

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

1 Comment

Click here to post a comment