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

Question

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.

Algorithm for Heapify():

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.

Answer 1

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.