Recursion Tree
Method
BY: Manayal Afzal
Zainab Zahid
Introduction
Basic Idea
Examples
Discussion
Introduction
• A recursion tree is a diagram that shows how a recursive function
breaks a problem into subproblems.
It helps to visualize the total work done and find time complexity.
• It is used to solve recurrence relations that appear in recursive
algorithms (like Merge Sort, Quick Sort, etc.).
• It helps to visualize how a recursive algorithm divides a problem into
smaller parts and how much work is done at each level.
BASIC IDEA
• Write the recurrence relation.
• Draw a tree showing recursive calls at each level.
• Write the cost/work at each level.
• Sum all levels to find the total cost (time complexity)
•If Summing up all levels becomes complex, we can find upper bound by considering a perfectly full tree
Example :
T(n)=2T(n/2)+n
n/2
(n/2 * 1/2)=n/4
(n/4 * 1/2)=n/8
(n/4 * 1/2)=n/16
C(n/16) C(n/16) C(n/16) C(n/16) C(n/16) C(n/16) C(n/16) C(n/16)C(n/16) C(n/16) C(n/16) C(n/16) C(n/16) C(n/16) C(n/16)C(n/16)
n/2 + n/2 = 2n/2
=n
n/4 + n/4 + n/4 + n/4 = 4n/4
=n
n/8 + n/8 + n/8 + n/8 + n/8 + n/8 +
n/8 + n/8 = 8n/8
=n
.
.
.
Cost function on each step=n
16
8
Time N depends on the height of the
complexity 4 tree so
nlog2n= log2(16)
Total height of the=4
O(nlog2n)
2
1
Recursion Tree Method
T(n) = T(n/4) + T(n/2) + n2:
8
Recursion Tree Method
T(n) = T(n/4) + T(n/2) + n2:
T(n)
9
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
T(n/4) T(n/2)
10
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
T(n/16) T(n/8) T(n/8) T(n/4)
11
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(1)
12
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(1)
13
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(1)
14
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 n 2
256
…
(1)
15
Recursion Tree Method
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 n 2
256
…
(1) 2
Total = n 1 + +5
16
( 5
16
2
+( ) ( )
5
16
3
+ )
= (n2) geometric series
16
Recursion Tree Method
• As we found that it is sometime difficult to have a good guess in case
of substitution method.
• Drawing out the recursion tree as we did in the analysis of Merge
Sort is the straightforward way to have a good guess.
• In this method each node represents the cost of each sub problem
somewhere in the set of recursive function invocations. We sum all
the costs of sub problems at all levels of recursion to find the logical
guess for our solution.
17
• This method is more useful for describing the running time of
divide and conquer problems.
• This method is used to generate a very good guess which can be
later verified by the substitution method. However, you can use
a recursion tree method as a direct proof of a solution to the
recurrence.
18
THANK YOU
