heaps analysis of heapsort version recall that phase ii is when the values are in heap and extracted one at time to form the sorted list version phase ii of the heapsort algorithm is identical to version and has the same complexityo( log nversion phase on the other hand has changed from top down approach to building the heap in version to building the heap from the bottom up in version we claimed that the complexity of this new phase is (nwhere is the number of nodes in the list stated more formally we have this claim for perfect binary tree of height hcontaining ( - nodesthe sums of the lengths of its maximum comparison paths is ( -hconsider binary heaps of heights etc up to height from the example for version of the algorithm it should be clear the maximum path length for any call to __siftdownfromto will be determined as shown in table notice that ( - represents half the nodes in the final heap (the leaf nodesand that the max path length for half the nodes in the heap will be it is this observation that leads to more efficient algorithm for building heap from the bottom up if we could add up all these maximum path lengthsthen we would have an upper bound for the amount of work to be done during phase of version of this algorithm ( ( ( - - the value would be an upper bound of the work to be donethe sum of the maximum path lengths we can eliminate most of the terms in this sum with little manipulation of the formula the value of could be computed as using this formula we can write it as ( ( - - [( ( ( - if we line up the terms in the equation above (as they are lined up right now)we can subtract like terms in the first like term we see ( this simplifies to table maximum path length for __siftdownfromto level max path length of nodes at level - - - - - - - - this copy belongs to 'acha