[go: up one dir, main page]
Scribd
Upload
136 views22 pages

Recurrence Tree Method

The document discusses the Divide and Conquer algorithm, specifically focusing on the Recursion Tree method for solving recurrences. It explains how to draw a recurrence tree, identify patterns in the series, and provides examples of solving specific recurrence equations. The document concludes with a notation related to the complexity of the algorithm.

Uploaded by

Raj Barasara
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
136 views22 pages

Recurrence Tree Method

The document discusses the Divide and Conquer algorithm, specifically focusing on the Recursion Tree method for solving recurrences. It explains how to draw a recurrence tree, identify patterns in the series, and provides examples of solving specific recurrence equations. The document concludes with a notation related to the complexity of the algorithm.

Uploaded by

Raj Barasara
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/ 22

Unit -2

Divide and
Conquer
Algorithm

Prepared by:
Rachana R. Buch
• In this method, we draw a Recurrence Tree
Recursion and calculate the time taken by every level of
Tree tree.
• Finally, we make the total of the work done
Method at all the levels.
● To draw the recurrence tree, we start from the given
equation of the recurrence and keep drawing till we find a
pattern.
● The pattern is typically an arithmetic series or geometric
series.
Equation of Arithmetic series

How to
draw a
Recurrence Equation of Geometric series
Tree ?
● Solve the following recurrence using
Recursion tree method
T(n) = 2T(n/2) + n2

Examples -
1
Continue
Note
Note
Note
Note
● Solve the following recurrence using
Recursion tree method
T(n) = 3T(n/3) + n3

Examples - 2
Continue
Continue
● Solve the following recurrence using
Recursion tree method
T(n) = 3T(n/4) + n2

Examples - 3
Continue
Continue
Continue
Examples -
4
Examples - 4
Continue…

Notation: O(n*log 5/42)


Example -5
Continue…
Thank
You

You might also like