Show that the worst case runtime of HeapSort is both .

Given psuedocode,

Use the power series summation formula:

CLRS already shows the proof for Build-Max-Heap being O(n). I need help with deriving runtime of Heapify inside of

the for loop using the power series summation formula.

For the Worst Case scenario in big O terms, the binary tree's most bottom level is full so I got that the

max # of nodes is represented by where h is height of tree. Then I got to here and got stuck. How would the right part of the summation formula look like?

For the Worst Case scenario in big terms, the binary tree's most bottom level has only 1 node so I got that the

max # of nodes is represented by where h is height of tree. Then I got to here and got stuck. How would the right part of the summation formula look like?

O nlogn) and 2 (nlogn