# 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

## 1 Answer

It's a variable substitution.

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.

• Thank you for the answer. But, k is a constant right? But is it mathematically possible? Dec 28, 2020 at 14:00
• my question is, is that substitution method purely mathematical or are we using some other facts like may be 'i' and 'k' are related? Dec 28, 2020 at 14:10
• @MidhunrajRPillai I don't know about any mathematical rules for substituting variables in a summation expression (like the substitution rules for integrals). My reasoning was just that since both expressions run over the same set of values, their results would be equal. (because addition in real numbers are commutative). It is more clear if you remove the summation symbol (the sigma letter) and write down both expressions as a sum. (The left side is 2^1*(k-1) + 2^2*(k-2) ... 2^(k-1)*1, and the right side is the same thing but reversed. ) Dec 28, 2020 at 17:25
• Yeah got it. On expanding, getting the answer. Thank you. Dec 28, 2020 at 17:42