CS 316: ALGORITHMS
Lecture 4
Analysis Of Recursive
Algorithms
Prepared by: Assoc. Prof. Ensaf Hussein
Presented by:
Dr. Mohammed El-Said
Dr. Mai Hamdalla
OUTLINE
Analysis of recursive algorithms
• Substitution
• Iteration Method – Iteration Tree
• Master Method
Recursive Algorithms
• Factorial
• Fibonacci Sequence
• Tower of Hanoi
ANALYSIS OF MERGE SORT
ALGORITHM Mergesort(A, p, r )
IF p < r
THEN q = FLOOR[(p + r)/2]
MERGE_Sort (A, p, q) T(n/2)
MERGE_Sort (A, q + 1, r) T(n/2)
Time of Division
MERGE (A, p, q, r) θ(n) Time of Conquer
T(n) = 2T(n/2)
+ θ(n)
Θ(nlgn) recurrence relation
BINARY-SEARCH: RECURRENCE
BINARY-SEARCH (A, lo, hi, x)
if (lo > hi)
return FALSE constant time: c1
mid (lo+hi)/2 constant time: c2
if x = A[mid]
return TRUE constant time: c3
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1,same
x)
problem of
if ( x > A[mid] )
size n/2
BINARY-SEARCH (A, mid+1, hi, x)
same
problem of
T(n) = c + T( n / 2 ) Θ(lgn) size n/2 4
RECURRENCES
An equation that describes a function
in terms of its value on smaller
inputs.
T(n) = T(n-1) + n
Recurrences arise when an algorithm
contains recursive calls to itself
5
COMPUTE COMPLEXITY FOR
RECURSIVE ALGORITHMS
GENERAL PLAN FOR ANALYSIS
OF RECURSIVE ALGORITHMS
Decide on a parameter indicating an
input’s size
Identify the basic operation
Check whether the number of times the
basic operation is executed may vary on
different inputs of the same size. (If it may,
the worst, average, and best cases must be
investigated separately.)
Set up a recurrence relation with an
appropriate initial condition expressing the
number of times the basic operation is
executed.
Solve the recurrence (or, at the very least,
establish its solution’s order of growth).
METHODS FOR SOLVING
RECURRENCES
Iteration method
Recursion tree method
Master method
8
1. ITERATION METHOD
The basic idea is to:
- expand the recurrence and
- express it as a summation of terms
dependent only on n and the initial
conditions.
9
EXAMPLE(1): BINARY SEARCH RECURRENCE
Consider T(n) = c + T(n/2), and T(1) = θ(1).
T(n) = c + T(n/2) T(n/2) = c + T(n/4)
= c + c + T(n/4) T(n/4) = c + T(n/8)
= c + c + c + T(n/8) = 3c +
T(n/23)
...
When T(n/2k)=T(1) ?
T(n) = k c + T(n/2k) when n = 2k
k = log2n
= c log2n + T(1)
log2n lgn 10
EXAMPLE(2):
Consider the recurrence
T(n) = T(n-1) +1 , and T(1) = θ(1).
Solution:
Expanding the above terms
T(n) = T(n-1) +1 T(n-1) = T(n-
2) + 1 thus,
T(n) = (T(n-2)+1) +1 =T(n-2) + 2
T(n-2) = T(n-3) +
1. thus,
11
EXAMPLE(2):
T(n) = (T(n-3) +1) + 2 = T(n-3) + 3.
T(n-3) = T(n-4) + 1.
thus,
T(n) = T(n-4) +4 .
...
T(n) = T(n-k) + k.
T(n-k)= T(1)= θ(1), when k =n-1
Thus, T(n)=θ(1)+(n-1)=θ(n)
Hence, T(n)=θ(n) 12
EXAMPLE(3)
T (n) n 3T n / 4 T(n/4) = n/4 +3T(n/16)
n 3 n / 4 3T n /16 T(n/16)
= n/16 +3T(n/64
n 3 n / 4 3 n /16 3T n / 64
n 3 n / 4 9 n /16 27T n / 64
T (n) n 3n / 4 9n /16 27 n / 64 ... 3log4 n T (1)
log 4 n 1 i
3
n n log 4 3
i 0 4
4n o( n)
O ( n)
EXAMPLE(3)
n+3n/4+3 n/4 +3 n/4
T (n) n 2 3T 2 n / 34 3
2 2 3 3
+3 4
T(n/4 4
)
n+3n/4+3 n/4 +3 n/4 +……+3kT(n/4k)
T(n/4k
) will
n 3be nT(1) 3T taking
/ 4 By
n /16 n = 4k log a a
n
=n
k = log4n
n 3 n / 4 3 n /16 3T n / 64
n 3 n / 4 9 n /16 27T n / 64
T (n) n 3n / 4 9n /16 27 n / 64 ... 3log4 n T (1)
log 4 n 1 i
3
n n log 4 3
a logb m
= m logb a
i 0 4
=0.79 <1
4n o( n)
∞
O ( n) 𝑎
∑ =
𝑎𝑟 𝑖
1 −𝑟
(𝑟 <1)
𝑖= 0
2. THE RECURSION-TREE METHOD
Is a pictorial representation of an iteration
method which is in the form of a tree, where
at each level nodes are expanded.
Idea:
Each node represents the cost of a single
sub-problem.
Sum up the costs with each level to get
level cost.
Sum up all the level costs to get total cost.
Particularly suitable for divide-and-conquer
recurrence. 15
Best used to generate a good guess.
RECURSION TREE FOR T(N)=3T(N
/3)+(N)
T(n) cn
T(n) = 3T(n/3) + cn
T(n/3) T(n/3) T(n/3) T(n/3) = 3T(n/9)+c(n/3)
T(n/9) =3T(n/27)+c(n/9)
T(n) cn
c(n/3) c(n/3) c(n/3)
T(n/9) T(n/9) T(n/9) T(n/9)T(n/9)T(n/9) T(n/9)T(n/9)T(n/9)
Cost per level
Level # node cn
0 1
cn
c(n/3) c(n/3) 3cn/3
1 3 c(n/3)
2 32 32cn/9
c(n/9) c(n/9) c(n/9) c(n/9) c(n/9) c(n/9) c(n/9) c(n/9) c(n/9)
i 3i 3icn/3
17
i
h 3hT(1)T(1)T(1) T(1)T(1)T(1) 3h T(1)
Total T(n)
h 1
T(n) = 3hT(1) 3i cn / 3i 17
+ i 0 Note: T(1)= T(n/3h)
Size of problem at leaves :
n/3h = 1 → 3h = n → h = log3n T(1)= T(n/3h)
T(n) = 3h * T(1) +
T(n) = 3log3n * T(1) +
T(n) = n T(1) + cn. h
T(n) = n T(1) + cn . log3 n
T(n) = θ(n log n)
18
RECURSION TREE FOR T(N)=4T(N
/2)+(N)
T(n) cn
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) = 4T(n/2) + cn
T(n/2) = 4T(n/4)+c(n/2)
T(n/4) =4T(n/8)+c(n/4)
cn
c(n/2) c(n/2) c(n/2) c(n/2)
T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4)
Level # node cn cn
0 1
1 4 c(n/2) c(n/2) c(n/2) c(n/2) 4cn/2
2 42C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) C(n/4) 42cn/4
i 4i
4icn/2i = 2icn
h 4h T(1)T(1)T(1) T(1)T(1)T(1) 4h T(1)
T(1)= T(n/2h)
T(n) = 4h * T(1) +
Size of problem at leaves :
T(n) = 4h * T(1) +
n/2h = 1 → 2h = n → h = log2n
T(n) = 4log2n * T(1) + cn.
4log2n = nlog24 = n2
T(n) = n2 T(1) + c n.
T(n) = n2 T(1) + cn.
Geometric series s= a+ar+ar2+…+ark-1 = a=1, r = 2
1(2h – 1) / (2-1) = 2h – 1 = 2log2n – 1 = n – 1
T(n) = n2 + cn(n-1)
21
T(n) = θ(n2)
REFERENCES
Introduction to Algorithms, Second Edition by
Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest and Clifford Stein, The MIT Press © 2001
Chapter 4.3
