Solving recurrences

• Recurrences are a major tool for

analysis of algorithms.
• Divide and Conquer algorithms are
analyzable by recurrences.
• Also note, recurrence relations are used
to design algorithms for combinatorial
functions and can embody dynamic
programming idea.

1
Methods for Solving Recurrences
• Using Substitution and Mathematical
Induction

• Using Recursion-tree

• Using Master Theorem

2
 Example: Integer Multiplication

• Let X = A B and Y = C D where A,B,C

and D are n/2 bit integers
• Simple Method: XY = (2n/2A+B)(2n/2C+D)
• Running Time Recurrence
T(n) < 4T(n/2) + 100n

How do we solve it?

 Substitution method
The most general method:
1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
Example: T(n) = 4T(n/2) + 100n
• [Assume that T(1) = Q(1).]
• Guess O(n3) . (Prove O and W separately.)
• Assume that T(k)  ck3 for k < n .
• Prove T(n)  cn3 by induction.
 Example of substitution
T ( n) = 4T ( n / 2) + 100n
 4c(n / 2)3 + 100n
= (c / 2)n3 + 100n
= cn3 - ((c / 2) n3 -100n )
desired – residual
 cn 3 desired
whenever (c/2)n3 – 100n  0, for
example, if c  200 and n  1.
residual
 A tighter upper bound?
We shall prove that T(n) = O(n2).
Assume that T(k)  ck2 for k < n:
T (n) = 4T (n / 2) + 100n
 cn 2 + 100n
 cn2

for no choice of c > 0. Stuck?

 A tighter upper bound!
IDEA: Strengthen the inductive hypothesis.
• Subtract a low-order term.
Inductive hypothesis: T(k)  c1k2 – c2k for k < n.
T ( n) = 4T (n / 2) + 100n
 4(c1 (n / 2) 2 - c2 (n / 2)) + 100n
= c1n 2 - 2c2 n + 100n
= c1n 2 - c2 n - (c2 n -100n)
 c1n 2 - c2 n if c > 100.
2
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.
• The recursion-tree method can be
unreliable, just like any method that uses
ellipses (…).
• The recursion-tree method promotes
intuition, however.
 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
5 n2
(n/4)2 (n/2)2
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
5 n2
(n/4)2 (n/2)2
16
25 n 2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
256

…
Q(1)
 Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
5 n2
(n/4)2 (n/2)2
16
25 n 2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
256

…
Q(1) Total = n2
(
1 + 16
5 + ( ) + ( ) +
5 2
16
5 3
16
)
= Q(n2) geometric series
 Appendix: geometric series

n +1
1 - x
1 + x + x2 +  + xn = for x  1
1- x
1
1+ x + x + =
2
for |x| < 1
1- x
Recursion Tree of T(n)=T(n/3)+ T(2n/3)+O(n)

20
 Master Theorem
• Let T(n) be a monotonically increasing function that
satisfies
T(n) = a T(n/b) + f(n)
T(1) = c
where a  1, b  2, c>0. If f(n) is Q(nd) where d  0
then
if logb a < d or a < bd

T(n) = if logb a = d or a = bd

if logb a > d or a > bd

21
22
 Recursion Tree for T(n)=3T(n/4)+Q(n2)
T(n) cn2 cn2

T(n/4) T(n/4) T(n/4) c(n/4)2 c(n/4)2 c(n/4)2

T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16)

(a) (b) (c)
cn2 cn2

c(n/4)2 c(n/4)2 (3/16)cn2

c(n/4)2

log 4n (3/16)2cn2
c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2

T(1)T(1)T(1) T(1)T(1)T(1) Q(nlog 43)

3log4n= nlog 43 Total O(n2)
(d) 23
 Solution to T(n)=3T(n/4)+Q(n2)
• The height is log4 n,
• #leaf nodes = 3log 4n= nlog 43. Leaf node cost: T(1).
• Total cost T(n)=cn2+(3/16) cn2+(3/16)2 cn2+
 +(3/16)log 4n-1 cn2+ Q(nlog 43)
= (1+3/16+(3/16)2+  +(3/16)log 4n-1) cn2 + Q(nlog 43)
< (1+3/16+(3/16)2+  +(3/16)m+ ) cn2 + Q(nlog 43)
= (1/(1-3/16)) cn2 + Q(nlog 43)
= 16/13cn2 + Q(nlog 43)
= O(n2).
T(n)=3T(n/4)+Q(n2)
24
Basis problems cost
Divide and combine cost 27
 Master Theorem: Pitfalls
• You cannot use the Master Theorem if
– T(n) is not monotone, e.g. T(n) = sin(n)
– f(n) is not a polynomial, e.g., T(n)=2T(n/2)+2n
– b cannot be expressed as a constant, e.g.

28
 Master Theorem: Example 1
• Let T(n) = T(n/2) + ½ n2 + n. What are the parameters?
a= 1
b= 2
d= 2

Therefore, which condition applies?

0 < 2 or 1 < 22, case 1 applies (if logb a < d or a < bd)

• We conclude that
T(n)  Q(nd) = Q (n2)

29
 Master Theorem: Example 2
• Let T(n)= 2 T(n/4) + n + 42. What are the parameters?
a= 2
b= 4
d = 1/2

Therefore, which condition applies?

½ = ½ or 2 = 41/2, case 2 applies (if logb a = d or a = bd)

• We conclude that

30
 Master Theorem: Example 3
• Let T(n)= 3 T(n/2) + 3/4n + 1. What are the parameters?
a= 3
b= 2
d= 1

Therefore, which condition applies?

log2 3 > 1 or 3 > 21, case 3 applies (if logb a > d or a > bd)

• We conclude that

• Note that log231.584…, can we say that T(n)  Q (n1.584)

No, because log231.5849… and n1.584  Q (n1.5849)

31
 ‘Fourth’ Condition
• Recall that we cannot use the Master Theorem if f(n),
the non-recursive cost, is not a polynomial.
• There is a limited 4th condition of the Master
Theorem that allows us to consider polylogarithmic
functions.
• Corollary: If for some k0 then

• This final condition is fairly limited and we present it

for sake of completeness.

32
 ‘Fourth’ Condition: Example
• Say we have the following recurrence relation
T(n)= 2 T(n/2) + n log n
• Clearly, a=2, b=2, but f(n) is not a polynomial.
However, we have f(n)Q(n log n), k=1
• Therefore, by the 4th condition of the Master
Theorem, we can say that

33
 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(cn/2)3  cn3 (reg. cond.) for c = 1/2.
 T(n) = Q(n3).

Ex. T(n) = 4T(n/2) + n2/lg n

a = 4, b = 2  nlogba = n2; f (n) = n2/lg n.
Master method does not apply. In particular,
for every constant e > 0, we have ne = W (lg n).
 Special Cases: Changing Variables
• Suppose T(n)=2T(n)+lg n.
• Rename m=lg n. So T(2m)=2T(2m/2)+m.
• Domain transformation:
S(m)=T(2m)
S(m)=2S(m/2)+m.
• So the solution is S(m)=O(m lg m).
• Changing back to T(n) from S(m), the solution is
T(n) =T(2m)=S(m)
=O(m lg m)
T(n) = O(lg n lg lg n)

44
 Using Iteration
T ( n) = T ( n ) + 1
T (2) = Q(1)

T (n) = 1 + T (n1/ 2 )
until....
= 1 + 1 + T (n ) 1/ 4

n (1/ 2i )
=2 //(log)
= i + ....T (n1/ 2i
)
 1/ 2i log n = log 2 = 1
= log log(n) + T (2)  2i = log n
= log log(n) + Q(1)  i = log log n
= Q(log log(n))
 Using Iteration:
Master Theorem does not apply

46
 Solving: (Second-degree) Linear
Homogeneous Recurrence Relations
• Assumptions
– Recurrence relation: an = c1an-1 + c2an-2
– Characteristic equation r2 – c1r – c2 = 0 has potentially two
distinct roots r1, r2.
• Theorem

{an} is a solution of the recurrence an = c1an-1 + c2an-2

if and only if

{an} is of the form an = b1r1n + b2r2n

for all n≥0, and for some constants b1, b2

47
 Example solution
• an = an-1 + 2an-2, a0=2 and a1=7
• Characteristic equation
r2 – r – 2 = 0
• The quadratic formula for ax2+bx+c = 0,
- b  b2 - 4ac
x=
2a
• Roots: r1=(1-(3))/2= -1 and r2=(1+(3))/2 = 2

48
 Example solution
• Therefore, solving for coefficients b1, b2
using initial values a0, a1 in
an = b1r1n + b2r2n
a1 - a0 r1 7 - 2  ( -1) 9
b2 = = = =3
r2 - r1 2 - ( -1) 3
a0 r2 - a1 2  2 - 7 - 3
b1 = = = = -1
r2 - r1 2 - ( -1) 3

an = b r + b r = -1  ( -1) + 3  2 = 3  2 - ( -1)
11
n
2 2
n n n n n

49
Summary: Master and Muster Theorem

50