# How to derive the worst case time complexity of Heapify algorithm?

I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure.

I am asking this question in the light of the book "Fundamentals of Computer Algorithms" by Ellis Horowitz et al. I am adding some screenshots of the algorithm as well as the derivation given in the book.

procedure $$HEAPIFY(A,n)$$
//Readjust the elements in A(1:n) to form a heap//
integer $$n,i$$
for $$i\leftarrow\lfloor n/2 \rfloor$$ to $$1$$ by $$-1$$ do
call $$ADJUST(A, i, n)$$
repeat
end $$HEAPIFY$$ Derivation for worst case complexity: I understood the first part and last part of this calculation but I cannot figure out how $$2^{i-1}(k-i)$$ changed into $$i 2^{k-i-1}$$.

All the derivations I can find in the internet takes a different approach by considering the height of the tree differently. I know that approach also leads to the same answer but I would like to know about this approach.

You might need the following information:

$$2^k-1 = n$$ or approximately $$2^k = n$$, where $$k$$ is the number of levels, starting from the root node and the level of root is 1 (not 0) and $$n$$ is the number of nodes.

Also the worst case time complexity of the Adjust() function is proportional to the height of the sub-tree it is called, that is $$O(log n)$$, where $$n$$ is the total number of elements in the sub-tree.

• The alii being Sartaj Sahni and Sanguthevar Rajasekaran. Dec 28, 2020 at 15:45

First, realize that in the leftmost side of the equation, the last term of the sum is zero (because when $$i = k$$, $$k-i = 0$$). So, the range of the first summation can be written as $$1 \le i \le k-1$$. Now, substitute $$i$$ with $$k-i$$. $$i$$ iterates over the set $${1, 2, ... , k-1}$$ and $$k-i$$ iterates over the set $${k-1, ... 2, 1}$$, they are the same set, so, we can do this.