RSS

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

So2^{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.

Advertisements
 
1 Comment

Posted by on August 20, 2012 in Algorithm

 

One response to “Why do subtrees have size at most 2n/3

  1. Mahesh

    February 18, 2016 at 9:14 AM

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

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: