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*):

The size of left subtree is:

Since

So

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

Advertisements

Mahesh

February 18, 2016 at 9:14 AM

But 2n/3 holds for only 1 level of recursion right?