Make Heap Best Case

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

    The Algorithm is:
    Code (Text):

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

    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
    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