Worst case in Max-Heapify - How do you get 2n/3?

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

Once that is clear, the bound of 2N/3 is easy to get.

Let us assume that the total number of nodes in the tree is N.

Number of nodes in the tree = 1 + (Number of nodes in Left Subtree) + (Number of nodes in Right Subtree)

For our case where the tree has last level half full, iF we assume that the right subtree is of height h, then the left subtree if of height (h+1):

Number of nodes in Left Subtree =1+2+4+8....2^(h+1)=2^(h+2)-1 .....(i)

Number of nodes in Right Subtree =1+2+4+8....2^(h) =2^(h+1)-1 .....(ii)

Thus, plugging into:

Number of nodes in the tree = 1 + (Number of nodes in Left Subtree) + (Number of nodes in Right Subtree)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

Plugging in this value into equation (i), we get:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

Hence the upper bound on the maximum number of nodes in a subtree for a tree with N nodes is 2N/3.

For a complete binary tree of height h, number of nodes is f(h) = 2^h - 1. In above case we have nearly complete binary tree with bottom half full. We can visualize this as collection of root + left complete tree + right complete tree. If height of original tree is h, then height of left is h - 1 and right is h - 2. So equation becomes

n = 1 + f(h-1) + f(h-2) (1)

We want to solve above for f(h-1) expressed as in terms of n

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

Using above in (1) we have

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

Hence O(2n/3)