For each level we use heapifyDown. assume S = 1/2 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) T = n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) = n * ( S - 1/2) S/2 = 1/4 + 1/8 + 2/16 + 3/32 + 5/64 + 8/128 + . . . S/4 = 1/8 + 1/16 + 2/32 + 3/64 + 5/128 + 8/256 + . . . 3S/4 = 1/4 + 2/8 + 3/16 + 5/32 + 8/64 + 13/128 + . . . = S - 1/2 Hence S = 2. and T = n * (S - 1/2) = 3/2 * n T is O(n) if("undefined"!==typeof hljs)hljs._ha();else if("undefined"===typeof hljsLoading){hljsLoading=1;var a=document.getElementsByTagName("head")[0],e=document.createElement("link");e.type="text/css";e.rel="stylesheet";e.href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.7.0/styles/default.min.css";a.appendChild(e);e=document.createElement("script");e.type="text/javascript";e.onload=function(){var d={},f=0;hljs._hb=function(b){b.removeAttribute("data-hljs");var c=b.innerHTML;c in d?b.innerHTML=d[c]:(7 ================================================================================================ http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf page 45 if("undefined"!==typeof hljs)hljs._ha();else if("undefined"===typeof hljsLoading){hljsLoading=1;var a=document.getElementsByTagName("head")[0],e=document.createElement("link");e.type="text/css";e.rel="stylesheet";e.href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.7.0/styles/default.min.css";a.appendChild(e);e=document.createElement("script");e.type="text/javascript";e.onload=function(){var d={},f=0;hljs._hb=function(b){b.removeAttribute("data-hljs");var c=b.innerHTML;c in d?b.innerHTML=d[c]:(7 A more formal math (Derivative) version

why buildHeap takes O(n)?

javaIsTheBest

For each level we use heapifyDown.

assume S = 1/2 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1)
T = n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )  = n * ( S - 1/2)

S/2   = 1/4 + 1/8 + 2/16 + 3/32 + 5/64 + 8/128 + . . .
S/4   =       1/8 + 1/16 + 2/32 + 3/64 + 5/128 + 8/256 + . . .
3S/4  = 1/4 + 2/8 + 3/16 + 5/32 + 8/64 + 13/128 + . . . = S - 1/2
Hence S = 2.
and T = n * (S - 1/2) = 3/2 * n 
T is O(n)

================================================================================================

http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
page 45

A more formal math (Derivative) version