TREE ANALYSIS FOR RECURRENCE

The Heapify recurrence is:

T(n) = T(2n/3) + Θ(1)

where 2/3 is the subproblem size on recurrence, based on the worst case problem size reduction occurring when the tree has 1/2 of a complete bottom row.

For a full binary tree of height i there are 2i+1-1 nodes.

of which 1/2 or 2i are on the left side.

A full binary tree of height i+1 has 2i+1 or 2*2i nodes at the bottom

or 2i on left with 1/2 full bottom.

A heap tree of height i+1 with 1/2 full bottom then has approximately (let's ignore the -1)

2i+1+ 2i = 2i*2+2i = 2i(2+1) = 3*2i nodes total

The worst case for a heap tree, the left side, has 2/3 of the nodes in the tree. For a heap of height i+1:

2i down the left side to height i

2i at the 1/2 left side bottom 

2i + 2i = 2*2i nodes

2*2i/3*2i = 2/3 of nodes are on left side.

 

The following table illustrates numerically the relative subproblem size reduction between the best and worst cases for a problem of various sizes of n.

Full Tree                                                           Half Full Last Level
            Nodes in Nodes in Size Ratio Ratio
      Left Right   Left Subtree Right Subtree Last Right Subtree Left Subtree
      Subtree Subtree Total Last Level Last Level Level is  with Tree with Tree
N Nodes Levels Nodes Nodes Nodes 1/2 Full 1/2 Full 1/2 Full Size Size
1 1 1                
2 3 2 1 1 3 1 0 2 0 0.5
3 7 3 3 3 7 3 1 5 0.2 0.6
4 15 4 7 7 15 7 3 11 0.272727273 0.636363636
5 31 5 15 15 31 15 7 23 0.304347826 0.652173913
6 63 6 31 31 63 31 15 47 0.319148936 0.659574468
7 127 7 63 63 127 63 31 95 0.326315789 0.663157895
8 255 8 127 127 255 127 63 191 0.329842932 0.664921466
9 511 9 255 255 511 255 127 383 0.331592689 0.665796345
10 1023 10 511 511 1023 511 255 767 0.332464146 0.666232073
11 2047 11 1023 1023 2047 1023 511 1535 0.332899023 0.666449511
12 4095 12 2047 2047 4095 2047 1023 3071 0.333116249 0.666558124
13 8191 13 4095 4095 8191 4095 2047 6143 0.333224809 0.666612404
14 16383 14 8191 8191 16383 8191 4095 12287 0.333279075 0.666639538
15 32767 15 16383 16383 32767 16383 8191 24575 0.333306205 0.666653103
16 65535 16 32767 32767 65535 32767 16383 49151 0.33331977 0.666659885
17 131071 17 65535 65535 131071 65535 32767 98303 0.333326552 0.666663276
18 262143 18 131071 131071 262143 131071 65535 196607 0.333329942 0.666664971
19 524287 19 262143 262143 524287 262143 131071 393215 0.333331638 0.666665819