recursion tree method.pdf

Recursion tree method is one of the finest method to solve the problem of design analysis.

1. Design and Analysis of Algorithms
Recurrence Relations
The Recursion Tree Method

2. Recursion Tree Method
•It is difficult to come up with good guess.
•Example of merge sort.
•In recursion tree
–Each node represents cost of single sub-problem
–We sum the cost with in each level of tree
–We sum all such level costs.
•Useful when the recurrence describes the running
time of divide and conquer algorithm.

3. •Use recursion treesto devise good guesses.
•Recursion Trees
–Show successive expansions of recurrences using
trees.
–Keep track of the time spent on the sub problems
of a divide and conquer algorithm.
–Help organize the algebraic bookkeeping
necessary to solve a recurrence.
Recursion Tree Method

4. Recursion Tree –Example
•Running time of Merge Sort:
T(n)= (1) ifn = 1
T(n)= 2T(n/2)+ (n)ifn > 1
•Rewrite the recurrence as
T(n)= c ifn = 1
T(n)= 2T(n/2)+ cn ifn > 1
c > 0:Running time for the base case and
time per array element for the divide and
combine steps.

5. Recursion Tree for Merge Sort
For the original problem,
we have a cost of cn,
plus two subproblems
each of size (n/2) and
running time T(n/2).
cn
T(n/2) T(n/2)
Each of the size n/2 problems
has a cost of cn/2 plus two
subproblems, each costing
T(n/4).
cn
cn/2cn/2
T(n/4)T(n/4)T(n/4)T(n/4)
Cost of divide and
merge.
Cost of sorting
subproblems.

6. Recursion Tree for Merge Sort
Continue expanding until the problem size reduces to 1.
cn
cn/2cn/2
cn/4 cn/4cn/4cn/4
ccc cc c
lg n
cn
cn
cn
cn
Total : cnlgn+cn

7. Recursion Tree for Merge Sort
Continue expanding until the problem size reduces to 1.
cn
cn/2cn/2
cn/4 cn/4cn/4cn/4
ccc cc c
•Each level has total cost cn.
•Each time we go down one level,
the number of sub problems
doubles, but the cost per sub
problem halves cost per level
remains the same.

8. Recursion Tree for Merge Sort
Continue expanding until the problem size reduces to 1.
cn
cn/2cn/2
cn/4 cn/4cn/4cn/4
ccc cc c
•There are lg n+ 1 levels, height is
lg n. (Assuming nis a power of 2.)
•Can be proved by induction.
•Total cost = sum of costs at each
level = (lg n+ 1)cn= cnlgn+ cn=
(n lgn).

9. •Best used to generate good guess.
•Verified using substitution method.
•For exampleT(n) = 3T(n/4) + (n
2
).
•Rewrite it
–T(n) = 3T(n/4) + cn
2
.
•We assume that nis an exact power of 4
Recursion Tree Method

10. T(n) = 3T(n/4) + c(n
2
).

11. T(n) = 3T(n/4) + c(n
2
).

12. T(n) = 3T(n/4) + c(n
2
).
•Sub problem sizes decrease as we get further from
the root
•We eventually must reach a boundary condition.
•How far from the root do we reach one?

13. T(n) = 3T(n/4) + c(n
2
).
•The sub problem size for a node at depth iis n/4
i
.
•Thus, the sub problem size hits n= 1
when n/4
i
= 1 or
equivalently, when i= log
4n.
•Thus, the tree has log
4n+ 1 levels (0, 1, 2,..., log
4n).

14. •Each level has three times more nodes than the level
above
•So the number of nodes at depth iis 3
i
.
•Because sub problem sizes reduce by a factor of 4 for
each level we go down from the root.
•Each node at depth i, for i= 0, 1, 2,..., log
4n-1, has a
cost of c(n/4
i
)
2
.
T(n) = 3T(n/4) + c(n
2
).

15. •Multiplying, we see that the total cost over all nodes
at depth i, for i= 0, 1, 2,..., log
4n-1, is
3
i
c(n/4
i
)
2
= (3/16)
i
cn
2
•The last level, at depth log
4n, has 3
log
4
n
=n
log
4
3
nodes,
each contributing cost T(1).
•Total Cost is n
log
4
3T(1)
, which is
(n
log
4
3T(1)
)
T(n) = 3T(n/4) + c(n
2
).