To solve this suppose that there is a almost complete binary tree (just for proving) ,tree will be having 1 more level on the left of it.
For eg.
Array :[1,3,2,4,5,6,7,8,9,10,11] just make the binary tree out of it, and you will be able to visualize it easily.
Now suppose you call Max-Heapify(Array,1) then you will be able to visualize from above example that every time the problem will get divided into a sub-problem of size 2n/3.Till we reach the leaves.
For Mathematical approach read below..
For a complete binary tree of height h, number of nodes is f(h) = 2^(h+1) - 1.--------------(a)
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(using a)
f(h-2) = 2^(h-1) - 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)/3
Which when n approaches to high values can be wrriten as O(2n/3).
Correct me if I am wrong.
