Make Heap Best Case

*khdani*

Hello,
I don't understand the proof of best case for Make Heap algorithm.

The Algorithm is:

Code:

Make_Heap(M[1...n])
for i= [tex]\left\lfloor n/2 \right\rfloor[/tex] to 1
Sift_Down(M[1...],i);

while the procedure Sift_Down is:

Code:

Sift_Down(M[1...n],i)
k=i;
repeat
j=k;
if 2j [tex]\leq[/tex] 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[tex]^{0}[/tex] + 2*2[tex]^{1}[/tex] + ... + 2*2[tex]^{k-2}[/tex]

so why not until 2[tex]^{k-1}[/tex], in Make_Heap procedure it iterates till the root ?
and why every term is multiplied by 2 ?

Thank You

Similar Threads for: Make Heap Best Case
Thread	Forum	Replies
Heap Pumps, Electrical Energy	General Physics	21
The shape of a heap of sand turns flat after being kicked...	Quantum Physics	0
Irritating heap corruption error in VC++2005	Programming & Comp Sci	0
Learn the general case first, or the special case first?	General Math	6
The Sorites heap paradox	General Discussion	8