0
$\begingroup$

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$

Algorithm for Adjust()

Derivation for worst case complexity:

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ The alii being Sartaj Sahni and Sanguthevar Rajasekaran. $\endgroup$
    – greybeard
    Dec 28 '20 at 15:45
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for the answer. But, k is a constant right? But is it mathematically possible? $\endgroup$ Dec 28 '20 at 14:00
  • $\begingroup$ my question is, is that substitution method purely mathematical or are we using some other facts like may be 'i' and 'k' are related? $\endgroup$ Dec 28 '20 at 14:10
  • $\begingroup$ @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. ) $\endgroup$
    – yemre
    Dec 28 '20 at 17:25
  • $\begingroup$ Yeah got it. On expanding, getting the answer. Thank you. $\endgroup$ Dec 28 '20 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.