# Make Heap Best Case

by khdani
Tags: case, heap
 P: 55 Hello, I don't understand the proof of best case for Make Heap algorithm. The Algorithm is: Make_Heap(M[1...n]) for i= $$\left\lfloor n/2 \right\rfloor$$ to 1 Sift_Down(M[1...],i);  while the procedure Sift_Down is: Sift_Down(M[1...n],i) k=i; repeat j=k; if 2j $$\leq$$ n and M[2j] > M[k] then k=2j; if 2j < n and M[2j+1] > M[k] then k=2j+1; Exchange M[k] and M[j] until k = j; the proof for the best case goes like this: t(n) <= 2*2$$^{0}$$ + 2*2$$^{1}$$ + ... + 2*2$$^{k-2}$$ so why not until 2$$^{k-1}$$, in Make_Heap procedure it iterates till the root ? and why every term is multiplied by 2 ? Thank You

 Related Discussions General Physics 21 Quantum Physics 0 Programming & Computer Science 0 General Math 6 General Discussion 8