Recurrence Analysis

What is a recurrence?
• A recurrence is an equation or inequality that describes a function in
terms of its value on smaller inputs.
Recurrence can take
many forms.

Equal split

unequal split: 2/3 to 1/3 split.

Not a constant fraction…

Substitution Methods for
Solving Recurrence
Substitution
method
The most general method: Example:
1. Guess the form of the solution.
2. Verify by induction. whenever (c/2)n3 – 100n ³ 0, for
3. Solve for constants. example, if c ³ 200 and n ³ 1.

T(n) = 4T(n/2) + 100n residual

• [Assume that T(1) = Q(1).] desired

• Guess O(n3) .
• Assume that T(k) £ ck3 for k < n .
• Prove T(n) £ cn3 by induction.
Example (continued)
• We must also handle the initial conditions,
that is, ground the induction with base
cases.
• Base: T(n) = Q(1) for all n < n0, where n0
is a suitable constant.
• For 1 £ n < n0, we have “Q(1)” £ cn3, if
we pick c big enough.

This bound, T(n) £ cn3, is not tight!

A tighter upper bound?
We shall prove that T(n) = O(n2).
Assume that T(k) £ ck2 for k < n:

for no choice of c > 0, we can say:

!!
A tighter upper bound!
IDEA: Strengthen the inductive hypothesis.
• Subtract a low-order term.
Inductive hypothesis: T(k) £ c1k2 – c2k for k < n.

Pick c1 big enough to handle the initial conditions.

Recursion-tree method
• A recursion tree models the costs (time) of a
recursive execution of an algorithm.
• The recursion tree method is good for
generating guesses for the substitution
method.
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

T(n)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

n2

T(n/4) T(n/2)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

n2

(n/4)2 (n/2)2

T(n/16) T(n/8) T(n/8) T(n/4)

Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

n2

(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

…

Q(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

n2
n2
(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

…

Q(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

n2
n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2
…

Q(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:

n2
n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 n 2
256

…
…

Q(1)
 n 1
1  x
1  x  x 2  ...  x n  for x ¹ 1
1 x
Example of recursion tree
1 x  x 2
 ... 
1
for |x| < 1
1 x
Solve T(n) = T(n/4) + T(n/2) + n2:

n2
n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 n 2
256

…
…

Q(1)
Total = n 1 2
 5
16  5 2
16
     ...
5 3
16
= O(n2) geometric series
The master method

The master method applies to recurrences of the form

T(n) = a T(n/b) + f (n) ,
where a ³ 1, b > 1, and f is asymptotically positive.
Three common cases
Compare f (n) with nlogba:

1. f (n) = O(nlogba – e) for some constant e > 0.

• f (n) grows polynomially slower than nlogba
(by an ne factor).
Solution: T(n) = Q(nlogba) .
Three common cases
Compare f (n) with nlogba:

2. f (n) = Q(nlogba lgkn) for some constant k ³ 0.

• f (n) and nlogba grow at similar rates.
Solution: T(n) = Q(nlogba lgk+1n) .
Three common cases (cont.)
Compare f (n) with nlogba:
3. f (n) = W(nlogba + e) for some constant e > 0.
• f (n) grows polynomially faster than nlogba (by
an ne factor),
and f (n) satisfies the regularity condition that
a f (n/b) £ c f (n) for some constant c < 1.
Solution: T(n) = Q( f (n) ) .
Examples
Ex. T(n) = 4T(n/2) + n
a = 4, b = 2  nlogba = n2; f (n) = n.
CASE 1: f (n) = O(n2 – e) for e = 1.
 T(n) = Q(n2).

Ex. T(n) = 4T(n/2) + n2 a = 4, b = 2  nlogba =

n2; f (n) = n2.
CASE 2: f (n) = Q(n2lg0n), that is, k = 0.
 T(n) = Q(n2lg n).
Examples
Ex. T(n) = 4T(n/2) + n3
a = 4, b = 2  nlogba = n2; f (n) = n3.
CASE 3: f (n) = W(n2 + e) for e = 1
and 4(n/2)3 £ cn3 (reg. cond.) for c = 1/2.
 T(n) = Q(n3).
Non-Example
• Consider the recurrence: T(n) = 2T(n/2) + n lg n
• a = 2, b = 2
• So one might think that f(n) (= n lg n) is larger than n and hence case 3
applies here.
• But actually f(n) needs to be polynomially larger than n for case 3 to
be applied:  > 0.
• SO, Master Theorem does not apply here.