title: Skiena, The Algorithm Design Manual, regarding heapsort (page 111)
body: <p>I am Self Studying the "The Algorithm Design Manual" book. Im at the moment studying chapter 4 (HeapSort) and on Page 111 there is an equation that i cant wrap my head around</p>
  
  <p>it goes like </p>
  
  <blockquote>
    <p>Space efficiency thus demands that we not allow holes in our
    tree—i.e., that each level be packed as much as it can be. If so, only
    the last level may be incomplete. By packing the elements of the last
    level as far to the left as possible, we can represent an n-key tree
    using exactly n elements of the array. If we did not enforce these
    structural constraints, we might need an array of size 2n to store the
    same elements. Since all but the last level is always filled, the
    height h of an n element heap is logarithmic because:  
    <a href="https://i.stack.imgur.com/qrxZi.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qrxZi.gif" alt="enter image description here"></a>so h =     lg n</p>
  </blockquote>
  
  <p>What i don't understand is how one can determine h =logn from the above equation? my math is rusty but to my knowledge  it should be like h =log((n+1)/2)</p>
  
  <p>I hope there are people here who have gone through this book and would be able to help me out understanding this</p>
  
  <p>Thanks in advanced</p>