Time Complexity of Recursive Algorithms
Recurrence Relation
Time Complexity of Recursive Algorithms Example 1
Consider the following algorithm:
int factorial ( int n ) {
if (n = = 0 )
return 1;
else
return n * factorial (n-1);
}
Recurrence Relation:
T(n) = T(n-1) + 1 for n>1
T(0) = 1 for n=0
Time Complexity of Recursive Algorithms Example 1
T(0) = 1 for n=0 T(n) ¿ 𝑻 (𝒏 −𝟏)+ 1
T(n) ¿ 𝑇 (𝑛 − 1) + 1 1
¿ 𝑇 (𝑛 −2) + 1
] +1
+1
T(n) ¿ 𝑻 (𝒏 −𝟏)+ 1
+2 2
¿ 𝑇 (𝑛 −3) + 1
] +2
+2
+3 3
-------------------
+k k
Time Complexity of Recursive Algorithms Example 1
T(0) = 1 for n=0
Only we have T(0) = 1
T(n) ¿ 𝑇 (𝑛 − 1) + 1 1
𝒏− 𝒌=𝟎
+2 2
𝒏=𝒌
+3 3
-------------------
+k k
+n
+n
¿ 1+n = n+1
Time Complexity of Recursive Algorithms Example 2
Consider the following algorithm:
void function ( int n ) { Recurrence Relation:
if (n >0) { T(n) = T(n-1) + n for n>0
for (i = 1 to n)
---------- T(0) = 1 for n=0
function ( n-1 );
}
}
Time Complexity of Recursive Algorithms Example 2
T(n) = 1 for n=0 T(n) ¿ 𝑻 (𝒏 −𝟏)+ n
T(n) ¿ 𝑇 (𝑛 − 1) + n 1
¿ 𝑇 (𝑛 −2) + n-1
] +n
+n 2 T(n) ¿ 𝑻 (𝒏 −𝟏)+ n
] +n ¿ 𝑇 (𝑛 −3) + n-2
++n 3
-------------------
¿ 𝑇 (𝑛 − 𝑘 ) k
Time Complexity of Recursive Algorithms Example 2
T(n) = 1 for n=0 T(n) ¿ 𝑻 (𝒏 −𝟏)+ n
T(n) ¿ 𝑇 (𝑛 − 1) + n 1
¿ 𝑇 (𝑛 −2) + n-1
] +n
+n 2 T(n) ¿ 𝑻 (𝒏 −𝟏)+ n
] +n ¿ 𝑇 (𝑛 −3) + n-2
++n 3
-------------------
¿ 𝑇 (𝑛 − 𝑘 ) + . . .+ n k
Time Complexity of Recursive Algorithms Example 2
T(n) = 1 for n=0
Only we have T(0) = 1
T(n) ¿ 𝑇 (𝑛 − 1) + n 1
𝒏− 𝒌=𝟎
+n 2
𝒌=𝒏
++n 3
-------------------
¿ 𝑇 (𝑛 − 𝑘 ) + . . .+ n k
¿ 𝑇 (𝑛 − 𝒏) + . . .+ n
¿ 𝑇 ( 0) + . . . + n
¿ 1 + ¿1 + + ¿+
Time Complexity of Recursive Algorithms Example 3
Consider the following algorithm:
void function ( int n ) { Recurrence Relation:
if (n >0) { T(n) = T(n-1) + log n for n>0
for (i = 1`; i<n; i=i*2)
---------------------- T(0) = 1 for n=0
function ( n-1 );
}
}
Time Complexity of Recursive Algorithms T(n) ¿ 𝑻 (𝒏 −𝟏)+ log n
¿ 𝑇 (𝑛 −2) + log n-1
T(n) = 1 for n=0 T(n) ¿ 𝑻 (𝒏 −𝟏)+ log n
T(n) ¿ 𝑇 (𝑛 − 1) + log n 1 ¿ 𝑇 (𝑛 −3) + log n-2
log (n-1) + log n
¿ 𝑇 (𝑛 − 2 ) +log ( n −1+) log n 2
] + log n
+ log ( n −2) + log (n −1)+ log n 3
----------------------------------
¿ 𝑇 (𝑛 − 𝑘 ) k
Time Complexity of Recursive Algorithms T(n) ¿ 𝑻 (𝒏 −𝟏)+ log n
¿ 𝑇 (𝑛 −2) + log n-1
T(n) = 1 for n=0 T(n) ¿ 𝑻 (𝒏 −𝟏)+ log n
T(n) ¿ 𝑇 (𝑛 − 1) + log n 1 ¿ 𝑇 (𝑛 −3) + log n-2
log (n-1) + log n
¿ 𝑇 (𝑛 − 2 ) +log ( n −1 )+ log n 2
] + log n
+ log ( n −2) + log (n −1)+ log n 3
----------------------------------
¿ 𝑇 (𝑛 − 𝑘 ) + . . k
1 . 2 . 3 . 4 . . . . . . n ≤ nn = log 1 + log 2 . . .+ log (n-1)+log n
Time Complexity n! ≤ nn = log ( 1 . 2 . …. . (n-1) . n )
log n! ≤ log nn = log n!
T(n) = 1 for n=0 log n! ≤ n log n
Only we have T(0) = 1
T(n) ¿ 𝑇 (𝑛 − 1) + log n 1
𝒏− 𝒌=𝟎
¿ 𝑇 (𝑛 − 2 ) +log ( n −1 ) n
+ log 2
𝒌=𝒏
+ log ( n −2) + log (n −1)+ log n 3
----------------------------------
¿ 𝑇 (𝑛 − 𝑘 ) + . . . k
¿ 𝑇 (𝑛 − 𝑛 ) + . . .
¿ 𝑇 ( 0) + +...
¿ 1 +𝑙𝑜𝑔 𝑛!
Time Complexity of Recursive Algorithms Example 4
Consider the following algorithm:
Recurrence Relation:
HanoiTower ( n , source, dest, aux ) {
if (disk =1)
T(n) = 2 T(n-1) +
move disk from source to dest
else {
HanoiTower (n-1 , source, aux, dest )
move disk from source to dest
HanoiTower (n-1 , aux, dest, source)
}
}
Time Complexity of Recursive Algorithms Example 4
Consider the following algorithm:
Recurrence Relation:
HanoiTower ( n , source, dest, aux ) {
if (disk =1)
T(n) = 2 T(n-1) + 1 for n>1
move disk from source to dest T(1) = 1 for n=1
else {
HanoiTower (n-1 , source, aux, dest )
move disk from source to dest
HanoiTower (n-1 , aux, dest, source)
}
}
Time Complexity of Recursive Algorithms Example 4
T(1) = 1 for n=1 T(n) ¿ 𝟐 𝑻 (𝒏 − 𝟏)+ 1
T(n) ¿ 2 𝑇 (𝑛 −1) + 1 1
¿ 2 𝑇 (𝑛 −2)+ 1
¿2 ] +1
+1 2 T(n) ¿ 𝟐 𝑻 (𝒏 − 𝟏)+ 1
¿ 2 2] +1 ¿ 2 𝑇 (𝑛 −3)+ 1
+ +1 3
-------------------
¿ 2 𝑘 𝑇 ( 𝑛 −𝑘 ) k
Time Complexity of Recursive Algorithms Example 4
T(1) = 1 for n=1 T(n) ¿ 𝟐 𝑻 (𝒏 − 𝟏)+ 1
T(n) ¿ 2 𝑇 (𝑛 −1) + 1 1
¿ 2 𝑇 (𝑛 −2)+ 1
¿2 ] +1
+1 2 T(n) ¿ 𝟐 𝑻 (𝒏 − 𝟏)+ 1
¿ 2 2] +1 ¿ 2 𝑇 (𝑛 −3)+ 1
+ +1 3
-------------------
¿ 2 𝑘 𝑇 ( 𝑛 − 𝑘 )+ . . .+ k
Time Complexity = Example 4
T(1) = 1 for n=1 Assume
T(n) ¿ 2 𝑇 (𝑛 −1) + 1 𝑛=1+𝑘
𝑜𝑟 𝑘=𝑛 −1
T(n) ¿ 2 𝑘 𝑇 ( 𝑛 −𝑘 ) + . . .+ 𝒂(𝑟 n − 𝟏)
=
𝒓 −𝟏
T(n)¿ 2 n − 1𝑇 (𝑛 − 𝑛+1 +
) . . .+
=1
T(n) ¿ 2 n − 1𝑇 (1 ) + . . .+ r = 2
T(n)¿ 2 n − 1+ . . . + =1
¿ 2 0 + 21 + 2 2 + . . .+ 2 𝑛1
T(n) 𝟏(𝟐 n − 𝟏)
¿
𝟐 −𝟏
𝟏(𝟐 n −𝟏)
T(n) 𝟐 −𝟏 = 2 n
-1 ()
Time Complexity of Recursive Algorithms
References:
Appendix B: “Foundations of Algorithms” By Neapolitan
YouTube Link