Recurrence Relations

Birgit Vogtenhuber

1 Recurrence Relations
 Overview

• What are recurrence relations?

• Recall asymptotic notations: O, Ω, Θ

• Depict recurrence relations via recursion trees

• Three methods for solving recurrence relations

• Exercises

2 Recurrence Relations
 What are recurrence relations?
Recurrence relation: equation (or inequality) that describes
a function in terms of its values on smaller inputs, plus one
or more initial terms.
Example: factorial function
f (n) = n · f (n − 1) for n > 1, f (1) = 1
Example: fibonacci numbers
f (n) = f (n − 1) + f (n − 2) for n > 2, f (1) = f (2) = 1
Applications:
• representation of combinatorial relations
• analysis of memory consumption and running time of
algorithms

3 iv Recurrence Relations
 What are recurrence relations?
Recurrence relations in the context of runtime and memory (
consumption analysis:
Example: runtimeof Merge-Sort
Θ(1) for n = 1
T (n) =
2T (n/2) + Θ(n) for n ≥ 2

Wanted: explicit asymptotic bounds for T (n):

T (n) = Θ(f (n)), T (n) = O(f (n)), T (n) = Ω(f (n))
Initial values: constant size input only requires constant
runtime and memory. Hence we always have
T (c) = Θ(1) for c constant

3 viii Recurrence Relations

 Asymptotic notation
O(g(n)) = {f : N → R | ∃ c ∈ R+ , n0 ∈ N :
0 ≤ f (n) ≤ c · g(n) ∀n ≥ n0 }

c · g(n)

f (n)

4 ii Recurrence Relations
 Asymptotic notation
Ω(g(n)) = {f : N → R+ | ∃ c ∈ R+ , n0 ∈ N :
0 ≤ c · g(n) ≤ f (n) ∀n ≥ n0 }

f (n)

c · g(n)

4 iii Recurrence Relations

 Asymptotic notation
Θ(g(n)) = {f : N → R | ∃ c1 , c2 ∈ R+ , n0 ∈ N :
0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n) ∀n ≥ n0 }

c2 · g(n)

f (n)

c1 · g(n)

4 iv Recurrence Relations
 Asymptotic notation
Θ(g(n)) = {f : N → R | ∃ c1 , c2 ∈ R+ , n0 ∈ N :
0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n) ∀n ≥ n0 }
Θ(g(n)) = O(g(n)) ∩ Ω(g(n)) c2 · g(n)

f (n)

c1 · g(n)

4v Recurrence Relations
 Asymptotic notation
O(g(n)) = {f : N → R | ∃ c ∈ R+ , n0 ∈ N :
0 ≤ f (n) ≤ c · g(n) ∀n ≥ n0 }

Ω(g(n)) = {f : N → R+ | ∃ c ∈ R+ , n0 ∈ N :
0 ≤ c · g(n) ≤ f (n) ∀n ≥ n0 }

Θ(g(n)) = {f : N → R | ∃ c1 , c2 ∈ R+ , n0 ∈ N :
0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n) ∀n ≥ n0 }
Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

4 vi Recurrence Relations
 Asymptotic notation
Asymptotic notation and limits

f (n) = O(g(n))

 0


f (n)  0 < c < ∞ f (n) = Θ(g(n)),
lim =
n→∞ g(n) 
 O(g(n)), Ω(g(n))

∞

f (n) = Ω(g(n))

f (n)
lim inf g(n) >0 f (n) = Ω(g(n))
n→∞
f (n)
lim sup g(n) < ∞(and ≥ 0) f (n) = O(g(n))
n→∞

if both are true: f (n) = Θ(g(n))

4 ix Recurrence Relations
 Asymptotic notation
Computing with asymptotic notation

• Addition:
Θ(f (n)) + Θ(g(n)) = Θ(max{f (n), g(n)})
P P

Θ(fi (n)) = Θ fi (n)
i i
Attention: not iteratively!
• Mulitplication:
c · Θ(f (n)) = Θ(f (n)) for constant c > 0
Θ(f (n)) · Θ(g(n)) = Θ(f (n) · g(n))

• Attention: equations always “from left to right”:

f (n) = Θ(g(n)) vs. Θ(g(n)) = f (n)
4 xv Recurrence Relations
 Methods to solve recurrence relations

• The iterative method

• The master method

• The substitution method

5 Recurrence Relations
 The iterative method
Idea: repeatedly plug in recurrence
n


Example: T (n) = 2T 2 + n2
n n 2




= 2 2T 4 + 2 + n2
n

n2
= 4T 4 + 2 + n2
n 2
n



n2
= 4 2T ( 8 + 4 + 2 + n2
n

n2 n2
= 8T 8 + 4 + 2 + n2 = . . .
n n2 n2


k
. . . = 2 T 2k + 2k−1 + · · · + 2 + n2
k−1
n 1


= 2k T + n2
P
2k 2i
i=0

6 ix Recurrence Relations
 The iterative method
k−1
n 1


T (n) = 2k T + n2
P
2k 2i
i=0
n
2k
= 1 implies k = log2 n
log2P
(n)−1
1
⇒ T (n) = 2log2 (n) T (1) + n2 2i
i=0

log2P
(n)−1
1
= n · Θ(1) + n2 2i
i=0

= n · Θ(1) + n2 · Θ(1) = Θ(n) + Θ(n2 )

⇒ T (n) = Θ(n2 )

6 xvi Recurrence Relations

 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

T (n)

7 iv Recurrence Relations
 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

n2
T ( n2 ) T ( n2 )

7v Recurrence Relations
 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

n2
( n2 )2 ( n2 )2

T ( n4 ) T ( n4 ) T ( n4 ) T ( n4 )

7 vi Recurrence Relations
 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

n2
( n2 )2 ( n2 )2

( n4 )2 ( n4 )2 ( n4 )2 ( n4 )2
···

T (1) ··· T (1)

7 vii Recurrence Relations

 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

n2
( n2 )2 ( n2 )2

( n4 )2 ( n4 )2 ( n4 )2 ( n4 )2
···

Θ(1) ··· Θ(1)

7 viii Recurrence Relations

 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

n2
( n2 )2 ( n2 )2

( n4 )2 ( n4 )2 ( n4 )2 ( n4 )2
log2 (n) ···

Θ(1) ··· Θ(1)

n leaves
7 ix Recurrence Relations
 Recursion trees
Visualization of a recurrence: recursion tree
Example: again T (n) = 2T ( n2 ) + n2

n 2 n2
( n2 )2 ( n2 )2 1 2
2n

( n4 )2 ( n4 )2 ( n4 )2 ( n4 )2 1 2
log2 (n) 4n

···
···

Θ(1) ··· Θ(1) Θ(n)

n leaves Total: Θ(n2 )

7 xi Recurrence Relations
 The master method
”cooking recipe” to solve recurrences of the form
n
T (n) = aT ( ) + f (n)
b
with a ≥ 1 and b > 1.
In the following cases we directly get the solution ...
logb a−ε


Case 1: f (n) = O n for some ε > 0
⇒ T (n) = Θ(nlogb a )
Case 2: f (n) = Θ(nlogb a ) ⇒ T (n) = Θ(nlogb a log n)
logb a+ε


Case 3: f (n) = Ω n for some ε > 0
and ∃c < 1 such that a · f ( nb ) ≤ c · f (n), n ≥ n0
⇒ T (n) = Θ(f (n))
8 ix Recurrence Relations
 The master method
Example 1: T (n) = 4T ( n2 ) + Θ(n)

parameter: a = 4, b = 2, f (n) = Θ(n) = Θ(n1 )

logb (a) = log2 (4) = 2, nlogb (a) = n2

compare f (n) with nlogb (a) :

1 ? 2−ε for 2 − ε ≥ 1, 1 ≥ ε
f (n) = Θ(n ) = O(n )
⇒ Yes: ε = 1
?
= Θ(n2 ) ⇒ No
? for 2 + ε ≤ 1, ε ≤ −1
= Ω(n2+ε )
⇒ No
⇒ Case 1 ⇒ T (n) = Θ(nlogb (a) ) = Θ(n2 )

8 xix Recurrence Relations

 The master method
Example 2: T (n) = 4T ( n2 ) + Θ(n2 )
parameter: a = 4, b = 2, f (n) = Θ(n2 )
logb (a) = log2 (4) = 2, nlogb (a) = n2

compare f (n) with nlogb (a) :

2 ? 2−ε for 2 − ε ≥ 2, 0 ≥ ε
f (n) = Θ(n ) = O(n )
⇒ No
?
= Θ(n2 ) ⇒ Yes
? for 2 + ε ≤ 2, ε ≤ 0
= Ω(n2+ε )
⇒ No
⇒ Case 2 ⇒ T (n) = Θ(nlogb (a) log(n)) = Θ(n2 log(n))

8 xxix Recurrence Relations

 The master method
Example 3: T (n) = 3T ( n2 ) + Θ(n2 )
parameter: a = 3, b = 2, f (n) = Θ(n2 )
logb (a) = log2 (3), 1 < log2 (3) < 2
nlogb (a) = nlog2 (3)
compare f (n) with nlogb (a) :
2 ? log2 (3)−ε for log2 (3) − ε ≥ 1,
f (n) = Θ(n ) = O(n )
log2 (3) − 2 ≥ ε
⇒ No
?
= Θ(nlog2 (3) ) ⇒ No
= Ω(nlog2 (3)+ε ) for log2 (3) + ε ≤ 2,
?
ε ≤ 2 − log2 (3)
⇒ Yes ⇒ Case 3?
8 xxxviii Recurrence Relations
 The master method
Example 3: T (n) = 3T ( n2 ) + Θ(n2 )
parameter: a = 3, b = 2, f (n) = Θ(n2 )
logb (a) = log2 (3), 1 < log2 (3) < 2
nlogb (a) = nlog2 (3)
f (n) = Θ(n2 ) = Ω(nlog2 (3)+ε )
Check additional condition:
∃c < 1 such that a · f ( nb ) ≤ c · f (n) for n ≥ n0 ?
a · f ( nb ) = 3 · ( n2 )2 = 3
4 · n2 ≤ c · n2
3
⇒ Yes for n ≥ 1 and 4 ≤c<1
⇒ Case 3 ⇒ T (n) = Θ(f (n)) = Θ(n2 )

8 xlii Recurrence Relations

 Recursion tree for the master method
Some intuition why the master method is actually correct
T (n) = aT ( nb ) + f (n)
f (n)
...
T ( nb ) T ( nb )
a times

9v Recurrence Relations
 Recursion tree for the master method
Some intuition why the master method is actually correct
T (n) = aT ( nb ) + f (n)
f (n)
...
f ( nb ) f ( nb )
... ... ...
T ( bn2 ) T ( bn2 ) T ( bn2 ) T ( bn2 )
a2 times

9 vi Recurrence Relations
 Recursion tree for the master method
Some intuition why the master method is actually correct
T (n) = aT ( nb ) + f (n)
f (n) f (n)
...
f ( nb ) f ( nb ) a · f ( nb )
... ... ...
f ( bn2 ) f ( bn2 ) f ( bn2 ) f ( bn2 ) a2 · f ( bn2 )
logb (n) ... ... ... ... ... ... ...

···
···

Θ(1) ··· Θ(1) Θ(nlogb a )

alogb n = nlogb a leaves

9 ix Recurrence Relations
 Recursion tree for the master method
Some intuition why the master method is actually correct
T (n) = aT ( nb ) + f (n)
f (n) f (n)
...
f ( nb ) f ( nb ) a · f ( nb )
... ... ...
f ( bn2 ) f ( bn2 ) f ( bn2 ) f ( bn2 ) a2 · f ( bn2 )
logb (n) ... ... ... ... ... ... ...

···
···

Θ(1) ··· Θ(1) Θ(nlogb a )

Plogb (n)−1
Total: Θ(n logb a
)+ i=0 ai · f ( bni )
9x Recurrence Relations
 The substitution method
Idea: ”guess” an asymptotic bound (O, Ω) and prove it by
mathematical induction
Example: T (n) = 2T (b n2 c) + n
Guess: T (n) = O(n log n)
We have to show: ∃c > 0, n0 ∈ N such that
T (n) ≤ c·n log n for all n ≥ n0
Induction hypothesis: T (n) ≤ c·n log2 n for some const. c > 0
Induction base: T (k) = Θ(1) ≤ d for small constant k
and some constant d > 0 (by def.)
Induction step: T (n) = 2T (b n2 c) + n
?
≤ 2 · (c ·b n2 c log2 b n2 c) + n ≤ c · n log2 n
10 viii Recurrence Relations
 The substitution method
?
Example: T (n) = 2T (b n2 c) + n, T (n) = O(n log n)
T (n) = 2T (b n2 c) + n
n n


≤ 2 · cb 2 c log2 (b 2 c) + n
≤ c · n log2 ( n2 ) + n
= c · n log2 n − c · n log2 2 + n
= c · n log2 n − c · n + n
= c · n log2 n + (1 − c) · n
≤ c · n log2 n for c ≥ 1
Choose k ≥ 3 for induction base, c ≥ max{1, d}, n0 ≥ 2
⇒ T (n) = O(n log n) from induction base
10 xvii Recurrence Relations
 The substitution method
Attention:
Don’t use asymptotic notation in the induction step!
Example again: T (n) = 2T (b n2 c) + n
Guess: T (n) = O(n)
⇒ Show: ∃c > 0, n0 ∈ N : T (n) ≤ c·n for n ≥ n0
Induction hypothesis: T (n) ≤ c·n for some const. c > 0
Induction step:
T (n) = 2T (b n2 c) + n
≤ 2(c · b n2 c) + n
≤ c · n + n = (c + 1) · n = O(n) WRONG !!

10 xxvii Recurrence Relations

 The substitution method
Attention:
Sometimes the “obvious” induction hypothesis doesn’t work:
Example: T (n) = T (b n2 c) + T (d n2 e) + 1
Guess: T (n) = O(n)
⇒ Show: ∃c > 0, n0 ∈ N : T (n) ≤ c·n for n ≥ n0
Induction hypothesis: T (n) ≤ c·n for some const. c > 0
Induction step:
T (n) = T (b n2 c) + T (d n2 e) + 1
≤ c · b n2 c + c · d n2 e + 1
=c·n +1 > c·n ⇒ Induction fails

10 xxxiii Recurrence Relations

 The substitution method
Attention:
Sometimes the “obvious” induction hypothesis doesn’t work:
Example: T (n) = T (b n2 c) + T (d n2 e) + 1
Guess: T (n) = O(n)
⇒ Show: ∃c > 0, n0 ∈ N : T (n) ≤ c·n for n ≥ n0
Induction hypothesis: T (n) ≤ c·n for some const. c > 0
Induction step:
T (n) = T (b n2 c) + T (d n2 e) + 1
≤ c · b n2 c + c · d n2 e + 1
=c·n +1 > c·n ⇒ Induction fails
But: weaker hypothesis T (n) ≤ c · n − d with d ∈ R works
10 xxxiv Recurrence Relations
 The substitution method
Attention:
Sometimes the “obvious” induction hypothesis doesn’t work:
Example: T (n) = T (b n2 c) + T (d n2 e) + 1
Guess: T (n) = O(n)
⇒ Show: ∃c > 0, n0 ∈ N : T (n) ≤ c·n for n ≥ n0
Induction hypothesis: T (n) ≤ c·n for some const. c > 0, d ∈ R
Induction step: T (n) ≤ c · n − d
T (n) = T (b n2 c) + T (d n2 e) + 1
n n
−d
≤ c · b 2 c + c · d 2 e + 1 −2 · d
=c·n +1 > c·n ⇒ Induction fails
= c · n − d + (1 − d) ≤ c · n − d for d ≥ 1 X
10 xxxix Recurrence Relations
 The substitution method
Remarks:

• advantage: more powerful than the other two methods

• disadvantage: two proofs needed for Θ (O and Ω)

• How to make the right guess?

◦ similarity to known recurrence relations
◦ recursion tree
• How to get the right approach?
◦ look at additional function
◦ in case of doubt, try a second time

10 xliv Recurrence Relations

 Exercises
Resolve the following recurrence relations using the differnt
methods presented in this lecture (recall that T (c) = Θ(1)
for any constant c ≥ 0).
• T (n) = 8T (n − 2) + Θ(1) • T (n) = T ( n2 )
• T (n) = 8T (n − 2) • T (n) = 2T ( n2 ) + 1
• T (n) = T (n − 2) + Θ(n) • T (n) = 2T ( n2 ) + n
• T (n) = T (n − 2) + Θ(1) • T (n) = 2T ( n2 ) + n2
• T (n) = T (n − 2) • T (n) = 6T ( n2 ) + 2n3
• T (n) = 2T (n − 4) + Θ(1) • T (n) = 9T ( n3 ) + n2
• T (n) = 3T (n − 4) + Θ(1) • T (n) = 10T ( n6 )+Θ(1)

12 i Recurrence Relations
 Exercises
Consider the following recurrence relations (recall that
T (c) = Θ(1) for any constant c ≥ 0). Make a guess on
what should be the best possible asymptotic bounds for
each of them, based on equations for which you already
know the result and/or recursion trees. Try to prove your
guesses using the substitution method.
• T (n) = T (b n2 c) + T (d n2 e) + n
• T (n) = T ( n4 ) + T ( 3n
4 )+n
• T (n) = T ( n4 ) + T ( 3n
4 )+1
• T (n) = T ( n4 ) + T ( 3n
4 ) + n 2

• T (n) = T ( n3 ) + T ( 2n
3 ) + n 3

12 ii Recurrence Relations
 Summary
• Goal: learn methods to asymptotically solve recurrence
relations for runtime- and memory analysis
• Iterative method: convert recurrence into a summation
and bound the summation to solve the recurrence
• Master method: solve recurrences of the form
T (n) = aT ( nb ) + f (n)
(three different cases depending on f (n), a, and b)
• Substitution method: guess a bound and prove it via
induction (upper and lower bound separately)
• Recursion tree for visualization and intuition

Thank you for your attention.

13 Recurrence Relations