Scribd
Upload
0 views2 pages

Recurrence Tree Method Notes

The document explains how to solve the recurrence relation T(n) = 2T(n/2) + n using the recursion tree method. It details the construction of the recursion tree, the work done at each level, and concludes that the total work is n log2(n). The final answer is T(n) = (n log n).

Uploaded by

ramanya010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0 views2 pages

Recurrence Tree Method Notes

The document explains how to solve the recurrence relation T(n) = 2T(n/2) + n using the recursion tree method. It details the construction of the recursion tree, the work done at each level, and concludes that the total work is n log2(n). The final answer is T(n) = (n log n).

Uploaded by

ramanya010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Recurrence Relation - Recursion Tree Method

Recurrence Relation Solving - Using Recursion Tree Method

Q. Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method.

This is a common recurrence seen in divide and conquer algorithms like Merge Sort.

Step 1: Construct the Recursion Tree

At each level:

Level 0: 1 call of size n Work = n

Level 1: 2 calls of size n/2 Work = 2 (n/2) = n

Level 2: 4 calls of size n/4 Work = 4 (n/4) = n

Level 3: 8 calls of size n/8 Work = 8 (n/8) = n

... and so on

Observation: Each level does total work = n

Step 2: Count Number of Levels

We divide n repeatedly by 2 until we reach size = 1.

That gives log2(n) levels.

Step 3: Total Work

Work per level = n

Number of levels = log2(n)

Total Work = n log2(n)

Final Answer:
T(n) = (n log n)

Therefore, the recurrence T(n) = 2T(n/2) + n solves to (n log n) using the recursion tree method.

Tips for Exams:

- Always draw the tree or explain level-wise

- Mention total cost at each level

- Show number of levels = log2(n)

- Multiply levels cost to get total complexity

- Final boxed answer: (n log n)

You might also like