Question

The recurrence relation for MAX-HEAPIFY function of heapsort algorithm is T(n) <= T(2n/3) + O(1). How is it 2n/3 ?

Answer 1

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.
 

   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.

Comments

Can you generate the above mentioned recurrence relation please explain this part "The ratio is (2k + 1)/(3k + 2),"? 

---

bottom level half full done

Answer 2

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.

Comments

Is this required for gate?

Answer 3

Follow this link for the derivation of recurrence relation