CSC2105: Algorithms

Recurrences
&
Master Method

Mashiour Rahman
Assistant Professor
[email protected]
American International University Bangladesh
 Recursion
• An object is recursive if
 it contains itself as part of it, or
 it is defined in terms of itself.
• Factorial: n!
 How do you compute 10!?
 n! = 1 * 2 * 3 *...* n
 n! = n * (n-1)!

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 2

 Factorial Function
• Pseudocode of factorial:
fac1
fac1
INPUT
INPUT::nn––aanatural
naturalnumber.
number.
OUTPUT
OUTPUT::n!n!(factorial
(factorialof
ofnn))
fac1(n)
fac1(n)
if
if nn << 22 then
then return
return 11
else
else return
return nn ** fac1(n-1)
fac1(n-1)

• A recursive procedure includes a

 Termination condition (determines when and
how to stop the recursion).
 One (or more) recursive calls.
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 3
 Tracing the Execution
fac1
fac1
INPUT
INPUT::nn––aanatural
naturalnumber.
number.
6 OUTPUT
OUTPUT::n!n!(factorial
(factorialof
ofnn))
fac(3)
3 * fac(2) fac1(n)
fac1(n)
if
if nn << 22 then
then return
return 11
else
else return
return nn ** fac1(n-1)
fac1(n-1)
2

fac(2)
2 * fac(1)

fac(1)
1
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 4
 Bookkeeping
• The computer maintains an activation stack for active
procedure calls ( compiler construction). Example
for fac(5).

fac(1) 1 =1

fac(2) 2*fac(1) 1 =2
fac(3) 3*fac(2) 2 =6

fac(4) 4*fac(3) 6 = 24

fac(5) 5*fac(4) 24 = 120

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 5

 Variants of Factorial
fac2
fac2 • fac2 is correct: The return
INPUT
INPUT::nn––aanatural
naturalnumber.
number.
OUTPUT statement in the if clause
OUTPUT::n! n!(factorial
(factorialof
ofn)
n)
terminates the function and,
fac
fac22(n)
(n) thus, the entire recursion.
if nn 
if 22 then
then return
return 11
return
return nn ** fac2(n-1)
fac2(n-1)

fac3
fac3 • fac3 is incorrect: Infinite
INPUT
INPUT::nn––aanatural
naturalnumber.
number.
OUTPUT
recursion. The termination
OUTPUT::n! n!(factorial
(factorialof
ofn)
n)
condition is never reached.
fac
fac33(n)
(n)
return
return nn ** fac3(n-1)
fac3(n-1)
if nn 
if 22 then
then return
return 11

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 6

 Mutual Recursion
• Recursion does not always occur because a
procedure calls itself.
• Mutual recursion occurs if two procedures call
each other.

B A

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 7

 Mutual Recursion Example
• Problem: Determine whether a given natural
number is even.

• Definition of even:
 0 is even (let)
 N is odd if N-1 is even
 N is even if N-1 is odd

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 8

 Implementation of even
even
even
INPUT
INPUT::nn––aanatural
naturalnumber
number..
OUTPUT
OUTPUT::true
trueififnnisiseven;
even;false
falseotherwise
otherwise
odd
odd(n)
(n)
if
if nn == 00 then
then return
return TRUE
TRUE
return
return !!even(n-1)
even(n-1)
even(n)
even(n)
if
if nn == 00 then
then return
return TRUE
TRUE
else
else return
return !!odd(n-1)
odd(n-1)

• Can it be used to determine whether a number

is odd?
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 9
 The divide- and- conquer design
paradigm

• Divide and conquer is just one of several

powerful techniques for algorithm design.
• Divide- and- conquer algorithms can be
analyzed using recurrences and the master
method (so practice this math).
• Can lead to more efficient algorithms

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 10

 Recurrences
• Running times of algorithms with recursive
calls can be described using recurrences.
• A recurrence is an equation or inequality that
describes a function in terms of its value on
smaller inputs.
• For divide and conquer algorithms:
 solving_trivial_problem if n  1
T ( n)  
num_pieces T ( n / subproblem_size_factor)  dividing  combining if n  1

• Example: Merge Sort  (1) if n  1

T ( n)  
2T (n / 2)  ( n) if n  1
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 11
 The divide- and- conquer design
paradigm

1. Divide the problem (instance) into

subproblems.
2. Conquer the subproblems by solving them
recursively.
3. Combine subproblem solutions.

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 12

 The divide- and- conquer
design paradigm
Example: merge sort
1. Divide: Trivial (array is halved).
2. Conquer: Recursively sort 2 subarrays.
3. Combine: Linear- time merge.
Recurrence for merge sort
Let T( n ) = Time required for size n Sub-
problem
Size (n/2)
T( n ) = 2 * T( n / 2) + O( n)
Number Of Time required for Work Dividing
+
Subproblems * each Subproblem and Combining

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 13

 The divide- and- conquer design
paradigm
Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Recurrence for binary search
 T( n) = 1 * T( n / 2) + Θ(1)
Number Of Time required for Work Dividing
+
Subproblems * each Subproblem and Combining

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 14

 Solving Recurrences
• Repeated (backward) substitution method
 Expanding the recurrence by substitution and
noticing a pattern (this is not a strictly formal proof).
• Substitution method
 guessing the solutions
 verifying the solution by the mathematical induction
• Recursion-trees
• Master method
 templates for different classes of recurrences

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 15

 Repeated Substitution
• Let’s find the running time of the merge sort
 1 if n  1
T ( n)  
 2T (n / 2)  n if n  1
T(n) = 2T(n/2) + n substitute assume 2k-1< n ≤ 2k.

= 2(2T(n/4) + n/2)
n/2 + n expand So upper bound for k is

= 22T(n/4) + 2n substitute n = 2k
= 22(2T(n/8) + n/4)
n/4 + 2n expand K = log n = lg n
2
= 23T(n/8) + 3n observe pattern
= 23T(n/23) + 3n observe pattern

T( n ) = 2kT(n/2k) + kn
= n T(n/n) + n lg n T(n) = O(nlgn)
= n + n lg n
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 16
 Repeated Substitution Method
• The procedure is straightforward:
 Substitute, Expand, Substitute, Expand, …
 Observe a pattern and determine the expression after
the k-th substitution.
 Find out what the highest value of k (number of iterations,
e.g., lg n) should be to get to the base case of the
recurrence (e.g., T(1)).
 Insert the value of T(1) and the expression of k into your
expression.
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 17
  2 if n  1
T ( n)  
2T (n / 2)  2n  3 if n  1

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 18

 Another Example…
 2 if n  1 assume 2k-1< n ≤ 2k.
T ( n)   So upper bound for k is
 2T ( n / 2)  2n  3 if n  1 n = 2k
T(n) = 2T(n/2) + 2n + 3 substitute K = log2n = lg n
= 2(2T(n/4) + n + 3)
3 + 2n +3 expand
= 22T(n/4) + 4n + 2x3 + 3 substitute
= 22(2T(n/8) + n/2 + 3)
3 + 4n + 2x3 + 3 expand
= 23T(n/23) + 2x3n + 3x(22+21+20) observe pattern
T(n) = 2kT(n/2k) + 2nk + 3  j 0
k 1 j
2
= 2kT(n/2k) + 2nk + 3 (2k-1)
= nT(n/n) + 2n lg n + 3(n - 1)
= 2n+2n lg n + 3n - 3
= 5n + 2n lg n – 3
T(n) = O(nlgn)
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 19
 Substitution Method
• The substitution method to solve recurrences
entails two steps:
 Guess the solution.
 Use induction to prove the solution.
• Example:
 T(n) = 4T(n/2) + n

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 20

 …Substitution Method
T(n) = 4T(n/2) + n
1) Guess T(n) = O(n3), i.e., T(n) is of the form cn3
2) Prove T(n)  cn3 by induction
T(n) = 4T(n/2) + n recurrence
 4c(n/2)3 + n induction hypothesis
= 0.5cn3 + n simplify
= cn3 – (0.5cn3 – n) rearrange
 cn3 if c>=2 and n>=1

Thus T(n) = O(n3)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 21

• Tighter bound for T(n) = 4T(n/2) + n:

Try to show T(n) = O(n2)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 22

 ...Substitution Method
• Tighter bound for T(n) = 4T(n/2) + n:

Try to show T(n) = O(n2)

Prove T(n)  cn2 by induction

T(n) = 4T(n/2) + n
 4c(n/2)2 + n
= cn2 + n
 cn2
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 23
 ...Substitution Method
• What is the problem? Rewriting
T(n) = O(n2) = cn2 + (something positive)

• As T(n)  cn2 does not work with the inductive

proof.
• Solution: Strengthen the hypothesis for the
inductive proof:
 T(n)  (answer you want) - (something > 0)
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 24
 ...Substitution Method
• Fixed proof: strengthen the inductive
hypothesis by subtracting lower-order terms:
Prove T(n)  cn2 - dn by induction

T(n) = 4T(n/2) + n
 4(c(n/2)2 – d(n/2)) + n
= cn2 – 2dn + n
= (cn2 – dn) – (dn – n)
 cn2 – dn if d
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 25
 Recursion Tree
• A recursion tree is a convenient way to visualize what
happens when a recurrence is iterated.
 Good for ”guessing” asymtotic solutions to recurrences

T (n)  T (n / 4)  T (n / 2)  n 2

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 26

 ...Recursion Tree

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 27

 Master Method
• The idea is to solve a class of recurrences that have the form
T(n) = aT(n/b) + f(n)
• Assumptions: a  1 and b > 1, and f(n) is asymptotically
positive.
• Abstractly speaking, T(n) is the runtime for an algorithm and
we know that
 a number of subproblems of size n/b are solved recursively, each in
time T(n/b).
 f(n) is the cost of dividing the problem and combining the results. e.g.,
In merge-sort T (n)  2T ( n / 2)  . (n)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 28

 …Master Method

alogb n

alogb n
Split problem into a parts. There are alogb n
logbn levels. There are a logb n  nlogb a leaves.
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 29
 …Master Method
• Iterating the recurrence (expanding the tree) yields
T(n) = f(n) + aT(n/b)
= f(n) + af(n/b) + a2T(n/b2)
= f(n) + af(n/b) + a2f(n/b2) + …
alogbn-1f(n/blogbn-1) + alogbnT(1)
logb n 1

T(n) =   
j j logb a
a f(n / b ) (n )
j 0

• The first term is a division/recombination cost (totaled across

all levels of the tree).
• The second term is the cost of doing all subproblems of size
1 (total of all work pushed to leaves).

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 30

 Master Method, Intuition
• Three common cases:
1. Running time dominated by cost at leaves.

2. Running time evenly distributed throughout the tree.

3. Running time dominated by cost at the root.

• To solve the recurrence, we need to identify the

dominant term.

• In each case compare with

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 31
 Master Method, Case 1
• If f (n)  O(nlog b a 
)for some constant   0 then
logb a
 f(n) grows polynomially slower than n (by

factor n ).
• The work at the leaf level dominates

Cost of all the leaves

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 32

 Master Method, Case 2
• If f (n)  (n ) then
log b a

 f (n) and n logb a are asymptotically the same

• The work is distributed equally throughout

the tree

(level cost)(number of levels)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 33

 Master Method, Case 3
• If f (n)  (n ) for some constant   0 then
logb a 

 Inverse of Case 1
logb a
 f(n) grows polynomially faster than n
 Also need a “regularity” condition
c  1 and n0  0 such that af (n / b)  cf (n) n  n0
• The work at the root dominates

division/recombination cost

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 34

 Master Theorem, Summarized
Given: recurrence of the form

1. f (n)  O n logb a  

 T (n)   nlogb a 

2. f (n)   nlogb a 

 T (n)   nlogb a lg n 
 
3. f (n)   nlogb a  and af ( n / b)  cf ( n), for some c  1, n  n0
 T ( n)    f (n) 

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 35

 Strategy
1. Extract a, b, and f(n) from a given recurrence
2. Determine nlogb a
3. Compare f(n) and nlogb a asymptotically
4. Determine appropriate MT case and apply it

Merge sort: T(n) = 2T(n/2) + (n)

1. a=2, b=2, f(n) = (n)
2. nlog22 = n
3. (n) = (n)
 Case 2: T(n) = (nlogbalog n) = (n log n)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 36

 Examples of Master Method

BinarySearch(A,
BinarySearch(A, l,l, r,
r, q):
q):
mm :=
:= (l+r)/2
(l+r)/2
if
if A[m]=q
A[m]=q then
then return
return mm
else
else ifif A[m]>q
A[m]>q then
then
BinarySearch(A,
BinarySearch(A, l, l, m-1,
m-1, q)
q)
else
else BinarySearch(A,
BinarySearch(A, m+1,
m+1, r,
r, q)
q)

T(n) = T(n/2) + 1
1. a=1, b=2, f(n) = 1
2. nlog21 = 1
3. 1 = (1)
 Case 2: T(n) = (log n)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 37

 ...Examples of Master Method

T(n) = 9T(n/3) + n
1. a=9, b=3, f(n) = n
2. nlog39 = n2
3. n = (nlog39 - ) with = 1
 Case 1: T(n) = (n2)

Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 38

 ...Examples of Master Method
T(n) = 3T(n/4) + n log n
1. a=3, b=4, f(n) = n log n

2. nlog43 = n0.792

3. n log n = (nlog43 + ) with = 0.208

 Case 3:

regularity condition: af(n/b) <= cf(n)

af(n/b) = 3(n/4)log(n/4) <= (3/4)nlog n = cf(n)
;with c=3/4
T(n) = (n log n)
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 39
 Is Recursion Necessary?
• Theory: You can always resort to iteration and
explicitly maintain a recursion stack.
• Practice: Recursion is elegant and in some cases the
best solution by far.
• Recursion is never appropriate if there exist simple
iterative solutions.
• Recursion is more expensive than corresponding
iterative solutions since bookkeeping is necessary.
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 40
 References & Readings
• CLRS
 Chapter: 4 (4.1-4.3)
 4.4 for bedtime reading
 Exercises
♦ 4.1, 4.2, 4.3
 Problems
♦ 4-1, 4-4
• HSR
 Chapter: 3 (3.1-3.6)
 Examples: 3.1-3.5
 Exercises: 3.1 (1, 2), 3.2 (1, 3-6),
Mashiour Rahman AIUB::CSC2105::Algorithm Recurrences 41