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
[ad type=”banner”]

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.

Categorized in:

Analysis of Algorithm

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , ,