Make Heap Best Case

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

    The Algorithm is:
    Code (Text):

    Make_Heap(M[1...n])
    [INDENT]
    for i= [tex]\left\lfloor n/2 \right\rfloor[/tex] to 1
    [INDENT]
    Sift_Down(M[1...],i);
    [/INDENT]
    [/INDENT]
     
    while the procedure Sift_Down is:
    Code (Text):

    Sift_Down(M[1...n],i)
    k=i;
    repeat
    [INDENT]
    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]
    [/INDENT]
    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
     
    Last edited: May 23, 2008
  2. jcsd
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted