## Why do subtrees have size at most 2n/3

20 Aug

Considering the worst case running time of Max-Heapify. At page 155 of Introduction to Algorithms 3rd edition, “The children’s subtrees each have size at most 2n/3 — the worst case occurs when the bottom level of the tree is exactly half full…”. Here’s the explanation why the size is at most 2n/3.

Heap is a complete binary tree. For a Heap of n nodes and x levels in the worst case scenario(the bottom level of the tree is exactly half full), the size of right subtree is(by the formula of geometric series):
$1+2+2^2+...+2^{x-3} =\frac{2^{x-2}-1}{2-1} =2^{x-2}-1$
The size of left subtree is:
$1+2+2^2+...+2^{x-3}+2^{x-2}=(2^{x-2}-1)+2^{x-2}=2\times2^{x-2}-1$

Since $n=(size\ of\ left\ subtree)+(size\ of\ right\ subtree)+1$
$n=(1+2+2^2+...+2^{x-3}+2^{x-2})+(1+2+2^2+...+2^{x-3})+1$
$n=(2\times2^{x-2}-1)+(2^{x-2}-1)+1$
$n=3\times2^{x-2}-1$

So$2^{x-2}=\frac{n+1}{3}$

$size\ of\ left\ subtree=2\times2^{x-2}-1=\frac{2n}{3}-\frac{1}{3}$

That’s why the children’s subtrees each have size at most 2n/3.