CSC 301 – Design and Analysis of Algorithms
Instructor: Anwar Ur Rehman
Lecture# 04(c): Recursion Tree Method
1
Recursion Tree Method
• Making a good guess is sometimes difficult with the substitution method.
• Recursion Tree Method can be used to devise a good guess.
• Recursion Trees show successive expansions of recurrences using trees.
• Recursion Trees model the costs (time) of a recursive execution of an algorithm
that is composed of two part:
• cost of non-recursive part.
• cost of recursive call on smaller input size.
• A Tree node represents the cost of a sub-problem (recursive function invocation).
• To determine the total cost of the Recursion Tree, evaluate:
• Cost of individual node at depth “i”
• Sum up the cost of all nodes at depth “i” 2
• Sum up all per-level costs of the Recursion Tree.
Recursion Tree Method: Example 1
{
1 𝑛=1
𝑇 (𝑛 )=
2𝑇 ( )
𝑛
2
+𝑛 𝑛>1
Solve the following recurrence using the Recurrence Tree Method.
Assumption: We assume that n is exact power of 2.
Logarithmic Identity (Exponent Rule):
The Geometric Series Formula:
3
The Infinite Geometric Series Formula:
Recursion Tree Method: Example 1
n
𝑇 (𝑛)=2 𝑇
𝑛
2 ( )
+𝑛
𝑛 𝑛 𝑛 T(n/2) T(n/2)
𝑇( )= 2.𝑇 ( 2 )+
2 2 2
4
Recursion Tree Method: Example 1
n
𝑇 (𝑛)=2 𝑇
𝑛
2 ( )
+𝑛
𝑛 𝑛 𝑛 n/2 n/2
𝑇( )= 2.𝑇 ( 2 )+
2 2 2
𝑛 𝑛 𝑛
𝑇( 2
)= 2.𝑇 ( 3
)+ 2 T(n/4) T(n/4) T(n/4) T(n/4)
2 2 2
4
Recursion Tree Method: Example 1
n
𝑇 (𝑛)=2 𝑇
𝑛
2
+𝑛 ( )
𝑛 𝑛 𝑛 n/2 n/2
𝑇( )= 2.𝑇 ( 2 )+
2 2 2
𝑛 𝑛 𝑛
𝑇( 2
)= 2.𝑇 ( 3
)+ 2 n/4 n/4 n/4 n/4
2 2 2
𝑇(
𝑛
𝑘 −1
)= 2.𝑇 (
𝑛
𝑘
)+
𝑛
𝑘 −1
...
2 2 2 T(n/8) T(n/8) T(n/8) T(n/8)
𝑛
𝑇 ( )= 𝑇 (1 )
…
…
𝑘
2
Continue expanding until the
T(1) problem size reduces to 1.
Total Cost = Cost of Leaf Nodes + Cost of Internal Nodes 4
Total Cost = Lc + Ic
Total Cost = (cost of leaf node x total leaf nodes) + (sum of costs at each level of internal nodes)
Recursion Tree Method: Example 1
n n
𝑇 (𝑛)=2 𝑇
𝑛
2
+𝑛 ( )
𝑛 𝑛 𝑛 n/2 n/2 n
𝑇( )= 2.𝑇 ( 2 )+
2 2 2
𝑛 𝑛 𝑛
𝑇( 2
)= 2.𝑇 ( 3
)+ 2 n/4 n/4 n/4 n/4 n
2 2 2
𝑛 𝑛 𝑛 ...
…
𝑇( 𝑘 −1
)= 2.𝑇 ( 𝑘
)+ 𝑘 −1
2 2 2 T(n/8) T(n/8) T(n/8) T(n/8)
𝑛
𝑇 ( )= 𝑇 (1 )
…
…
𝑘
2
𝑘
𝑛=2 ⟹ 𝑘=lg𝑛 T(1)
𝐼 𝑐 =𝑘 ∙ 𝑛
𝐼 𝑐 =𝑛 lg 𝑛 4
Total Cost = Lc + Ic ⟹ 𝑛+𝑛 lg 𝑛 𝐻𝑒𝑛𝑐𝑒:𝑇 (𝑛)∈Ο(𝑛lg𝑛)
Design & Analysis of Algorithms
8
Recursion Tree Method: Example 2
{
1 𝑛 =1
𝑇 (𝑛)=
2𝑇 ( )
𝑛
2
2
+𝑛 𝑛>1
Solve the following recurrence using the Recurrence Tree Method.
Assumption: We assume that n is exact power of 2.
5
Recursion Tree Method: Example 2
n2
𝑇 (𝑛)=2 𝑇 ( )
𝑛
2
+𝑛 2
𝑛 𝑛 𝑛
2
T(n/2) T(n/2)
𝑇 ( )= 2.𝑇 ( 2 )+ 2
2 2 2
5
Recursion Tree Method: Example 2
n2
𝑇 (𝑛)=2 𝑇 ( )
𝑛
2
+𝑛 2
𝑛 𝑛 𝑛
2
n2/4 n2/4
𝑇 ( )= 2.𝑇 ( 2 )+ 2
2 2 2
2
𝑛 𝑛 𝑛
𝑇 ( 2 )= 2. 𝑇 ( 3 )+ 2 T(n/4) T(n/4) T(n/4) T(n/4)
2 2 4
5
Recursion Tree Method: Example 2
n2 n2
𝑇 (𝑛)=2 𝑇 ( )
𝑛
2
+𝑛 2
𝑛 𝑛 𝑛
2
n2/4 n2/4 n2/2
𝑇 ( )= 2.𝑇 ( 2 )+ 2
2 2 2
2
𝑛 𝑛 𝑛
𝑇 ( 2 )= 2. 𝑇 ( 3 )+ 2 n2/16 n2/16 n2/16 n2/16 n2/4
2 2 4
𝑛 ...
…
𝑇 ( 𝑘
)= 𝑇 (1 )
2 T(n/8) T(n/8) T(n/8) T(n/8)
…
𝑘
…
𝑛=2 ⟹ 𝑘=lg𝑛 n2/2k-1
T(1)
[ ]
2 1 2
𝐼 𝑐 =𝑛 ∙ ⟹2 𝑛 5
1
1−
2
Total Cost = Lc + Ic ⟹ 𝑛+2 𝑛
2 2
𝐻𝑒𝑛𝑐𝑒:𝑇 (𝑛)∈ Ο(𝑛 )
Design & Analysis of Algorithms
13
Recursion Tree Method: Example 3
{
1 𝑛 =1
𝑇 (𝑛)=
3𝑇 ( )
𝑛
4
2
+ 𝑛 𝑛> 1
Solve the following recurrence using the Recurrence Tree Method.
Assumption: We assume that n is exact power of 4.
6
Recursion Tree Method: Example 3
n2
𝑇 (𝑛)=3 𝑇 ( )
𝑛
4
+𝑛2
𝑛 𝑛 𝑛
2 T(n/4) T(n/4) T(n/4)
𝑇 ( )= 3 .𝑇 ( 2 )+ 2
4 4 4
6
Recursion Tree Method: Example 3
n2
𝑇 (𝑛)=3 𝑇 ( )
𝑛
4
+𝑛2
𝑛 𝑛 𝑛
2 n2/16 n2/16 n2/16
𝑇 ( )= 3 .𝑇 ( 2 )+ 2
4 4 4
2
𝑛 𝑛 𝑛
𝑇 ( 2 )= 3 .𝑇 ( 3 )+ 2
4 4 16
6
Recursion Tree Method: Example 3
2
n2 𝑛
𝑇 (𝑛)=3 𝑇 ( )
𝑛
4
+𝑛2
3 2
𝑛 𝑛 𝑛
2 n /16
2
n /16
2
n /16
2 𝑛
𝑇 ( )= 3 .𝑇 ( 2 )+ 2 16
4 4 4
2
𝑛 𝑛 𝑛
2 n 2 n2 n 2 n 2 n2 n 2 n 2 n2 n 2
𝑇 ( 2 )= 3 .𝑇 ( 3 )+ 9 2
4 4 16 𝑛
256 256 256 256 256 256 256 256 256 256
𝑛
…
𝑇 ( 𝑘
)= 𝑇 (1 )
4
3𝑘 −1 2
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
𝑛
𝑛=4 𝑘 T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1)
16𝑘 −1
𝑘=log 4 𝑛
[( ) ( ) ( ) ( ) ]
0 1 2 𝑘 −1
𝑘 log 4 𝑛 log 4 3 2 3 3 3 3
𝐿𝑐 =3 ⟹ 3 ⟹𝑛 𝐼 𝑐 =𝑛 ∙
16
+
16
+
16
+⋅ ⋅ ⋅+
16
[ ]
2 1 16 2
𝐼 𝑐 =𝑛 ∙ ⟹ 𝑛 6
3 13
1−
Total Cost = Lc + Ic
16
log 4 3 16
⟹𝑛 + 𝑛2
13 2
𝐻𝑒𝑛𝑐𝑒:𝑇 (𝑛)∈ Ο(𝑛 )
Recursion Tree Method: Example 4
{
1 𝑛=1
𝑇 (𝑛)=
𝑇 ( )
𝑛
4
+𝑇
𝑛
2 ( )
2
+𝑛 𝑛>1
Solve the following recurrence using the Recurrence Tree Method.
7
Recursion Tree Method: Example 4
𝑇 (𝑛)=𝑇 ( ) + 𝑇 ( ) +𝑛
𝑛 𝑛 2 n 2
4 2
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+𝑇 ( )+ T(n/4) T(n/2)
4 16 8 16
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+ 𝑇 ( )+
2 8 4 4
7
Recursion Tree Method: Example 4
𝑇 (𝑛)=𝑇 ( ) + 𝑇 ( ) +𝑛
𝑛 𝑛 n2 2
4 2
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+𝑇 ( )+ n2/16 n2/4
4 16 8 16
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+ 𝑇 ( )+
2 8 4 4 T(n/16) T(n/8) T(n/8) T(n/4)
2
𝑛 𝑛 𝑛 𝑛
𝑇( )=𝑇 ( )+ 𝑇 ( )+
16 64 32 256
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+ 𝑇 ( )+
8 32 16 64
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+𝑇 ( )+
4 16 8 16
7
Recursion Tree Method: Example 4
𝑇 (𝑛)=𝑇 ( ) + 𝑇 ( ) +𝑛
𝑛 𝑛 n2 2
𝑛
2
4 2
2
𝑛 𝑛 𝑛 𝑛 5 2
𝑇 ( )= 𝑇 ( )+𝑇 ( )+ n /16
2
n /4
2 𝑛
4 16 8 16 16
2
𝑛 𝑛 𝑛 𝑛
𝑇 ( )= 𝑇 ( )+ 𝑇 ( )+ 25 2
2 8 4 4 n2/256 n2/64 n2/64 n2/16 𝑛
256
2
𝑛 𝑛 𝑛 𝑛
…
𝑇( )=𝑇 ( )+ 𝑇 ( )+
16 64 32 256 𝑘 −1
5
…
…
…
…
…
…
…
2
2 𝑛
𝑛
𝑇 ( )= 𝑇 (
𝑛
)+ 𝑇 (
𝑛
)+
𝑛 16𝑘 −1
8 32 16 64 T(1) T(1) T(1) T(1)
[( ) ( ) ( ) ( ) ]
2 0 1 2 𝑘 −1
𝑛
𝑇 ( )= 𝑇 (
𝑛 𝑛
)+𝑇 ( )+
𝑛 2 5 5 5 5
4 16 8 16
𝐼 𝑐 =𝑛 ∙ + + +⋅ ⋅ ⋅+
16 16 16 16
𝑛
[ ]
2 1 16 2
𝑇 ( )= 𝑇 (1 ) 𝐼 𝑐 =𝑛 ∙ ⟹ 𝑛
𝑘 5 11
2 1−
7
16
𝑘
𝑛=2 ⟹ 𝑘=lg 𝑛
Total Cost = Lc + Ic
16
⟹ 𝑛+ 𝑛2 2
11
𝐻𝑒𝑛𝑐𝑒:𝑇 (𝑛)∈Ο(𝑛 )
Recursion Tree Method: Example 5
{
1 𝑛=1
𝑇 (𝑛)=
𝑇 ( )
𝑛
3
+𝑇
2𝑛
3 (
+ 𝑛𝑛 >1)
Solve the following recurrence using the Recurrence Tree Method.
8
Recursion Tree Method: Example 5
𝑇 (𝑛)=𝑇 ( ) ( )
𝑛
3
+𝑇
2𝑛
3
+𝑛 n
𝑛 𝑛 2𝑛 𝑛
𝑇( )= 𝑇 ( )+ 𝑇 ( )+ T(n/3) T(2n/3)
3 9 9 3
2𝑛 2𝑛 4 𝑛 2𝑛
𝑇( )=𝑇 ( )+𝑇 ( )+
3 9 9 3
8
Recursion Tree Method: Example 5
𝑇 (𝑛)=𝑇 ( ) ( )
𝑛
3
+𝑇
2𝑛
3
+𝑛 n
𝑛 𝑛 2𝑛 𝑛
𝑇( )= 𝑇 ( )+ 𝑇 ( )+ n/3 2n/3
3 9 9 3
2𝑛 2𝑛 4 𝑛 2𝑛
𝑇( )=𝑇 ( )+𝑇 ( )+
3 9 9 3 T(n/9) T(2n/9) T(2n/9) T(4n/9)
𝑛 𝑛 2𝑛 𝑛
𝑇( )= 𝑇 ( )+𝑇 ( )+
9 27 27 9
2𝑛 2𝑛 4 𝑛 2𝑛
𝑇( )=𝑇 ( )+𝑇 ( )+
9 27 27 9
4𝑛 4𝑛 8𝑛 4𝑛
𝑇( )=𝑇 ( )+𝑇 ( )+
9 27 27 9
8
Recursion Tree Method: Example 5
𝑇 (𝑛)=𝑇 ( ) ( )
𝑛
3
+𝑇
2𝑛
3
+𝑛 n 𝑛
𝑛 𝑛 2𝑛 𝑛
𝑇(
3
)= 𝑇 ( )+ 𝑇 (
9 9
)+
3
n/3 2n/3 𝑛
2𝑛 2𝑛 4 𝑛 2𝑛
𝑇( )=𝑇 ( )+𝑇 ( )+
3 9 9 3 n/9 2n/9 2n/9 4n/9 𝑛
𝑛 𝑛 2𝑛 𝑛
…
𝑇( )= 𝑇 ( )+𝑇 ( )+
9 27 27 9
…
…
…
…
…
…
…
2𝑛 2𝑛 4 𝑛 2𝑛 𝑛
𝑇( )=𝑇 ( )+𝑇 ( )+ T(1) T(1) T(1) T(1)
9 27 27 9
4𝑛 4𝑛 8𝑛 4𝑛
𝑇(
9
)=𝑇 (
27
)+𝑇 (
27
)+
9
𝐼 𝑐 =𝑛 ∙ 𝑘
2
𝑘
3
𝑘 𝐼 𝑐 =𝑛 log 3 /2 𝑛
𝑇 ( 𝑘 𝑛)= 𝑇 (1)⟹ 𝑛= 𝑘
3 2⟹ 𝑘=log 3 /2 𝑛 8
Total Cost = Lc + Ic ⟹ 𝑛
𝑘
𝐿 𝑐 =2 ⟹ 2log 𝑛⟹ 𝑛log
3 /2 3 /2 2
log 3 / 2 2
𝑛( 𝑛 ) ∈ Ο ( 𝑛lg 𝑛 ) ? ?
+𝑛 log 3 / 2𝑇
Recursion Tree Method: Caution Note
• Recursion Trees are best used to generate good guesses.
• Verify guesses using the substitution method.
• A small amount of “sloppiness” can be tolerated.
• Using an infinite decreasing geometric series as an upper bound.
• Assuming “n” to be an exact power of 2, 3, or 4.
• By carefully drawing out a recursion tree and summing the costs, recursion
tree method can be used as a direct proof of a solution to any recurrence.
9
Practice Questions
Solve the following recurrences using the Recurrence Tree Method.
𝑇 (𝑛)= 4 𝑇 ( )
𝑛
2
+ 𝑛2
𝑇 (𝑛 )=2 𝑇 ( )+𝑛
𝑛
3
10
THANK YOU
11