Scribd
Upload
59 views2 pages

Recurrences Slides

The document discusses algorithms for solving recurrence relations. It describes three main methods: the substitution method, recursion tree method, and master method. The substitution method involves guessing a solution and proving it using induction. The recursion tree method generates a recursion tree to help guess solutions, especially for divide-and-conquer algorithms. The master method provides a theorem to classify and solve recurrences of the form T(n)=aT(n/b)+f(n) based on comparing f(n) to nlogba. Examples are given to illustrate each method.

Uploaded by

Iván Eduardo
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views2 pages

Recurrences Slides

The document discusses algorithms for solving recurrence relations. It describes three main methods: the substitution method, recursion tree method, and master method. The substitution method involves guessing a solution and proving it using induction. The recursion tree method generates a recursion tree to help guess solutions, especially for divide-and-conquer algorithms. The master method provides a theorem to classify and solve recurrences of the form T(n)=aT(n/b)+f(n) based on comparing f(n) to nlogba. Examples are given to illustrate each method.

Uploaded by

Iván Eduardo
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithms and Architecture 1 Recurrences

A recurrence is an equation or inequality that


describes a function in terms of its value on
smaller inputs.
Methods for solving recurrences:
 Substitution method
Recurrences  Recursion-tree method
 Master method
Alexandre David

1 2

The Substitution Method The Recursion-Tree Method

Two steps: Each node represents the cost of a single


 Guess the form of the solution subproblem.
 Use induction to find the constants and prove that the Useful when it describes the running time of a
solution works divide-and-conquer algorithm.
Problem: come up with a good guess Used to generate a good guess or as a direct
 Use recursion trees

proof of a solution to a recurrence.
Correct the guess
Example: T(n)=3T(n/4)+θ(n2)
 Construct recursion tree to obtain a guess
 Use the substitution method for the proof

3 4
The Master Method Master Method: Examples

For recurrences of the form T(n)=aT(n/b)+f(n) T(n)=9T(n/3)+n


where a≥1 and b>1 are constants and f(n) is a=9, b=3, f(n)=n
log a
n b n 3 n 
log 9 2

asymptotically positive. Case 1 with ε=1, we conclude T(n)=Θ(n2).
Theorem: T(n) can be bounded as follows
log b a
 if f  n O  n  for some ε>0 then T  n  nlog a  T(n)=T(2n/3)+1
 n 0 1
b

log a log 1
 if f  n  n  then T  n  nlog a lg n  f  n  lg n 
log a
b b a=1, b=2/3, f(n)=1 n b n 3 2
log a

 if f  n   n b
 for some ε>0 and if af(n/b)≤cf(n) for Case 2, we conclude T(n)=Θ(lg n).
some c<1 then T  n  f  n 
T(n)=3T(n/4)+nlgn n
log b a
n  O  n 0.793 

log 4 3

Intuition: compare f(n) to n


logb a
, the larger is the a=3, b=4, f(n)=nlgn f n    n  logb a

solution. Smaller: polynomially smaller by a factor Case 3, check regularity:


 af(n/b)=3(n/4)lg(n/4)≤(3/4)nlgn=cf(n).
of n . Larger: polynomially larger + “regularity”
condition. 5 We conclude T(n)=Θ(nlgn). 6

Master Method: Example Master Theorem: Proof Idea

T(n)=2T(n/2)+nlgn Proof for a sub-domain: n=1,b,b2,...


a=2, b=2, f(n)=nlgn, n
log a
n b
  compute the cost with a recursion tree (lemma 4.2)
leaves: lognn1logj a  j
b

Case 3?
f(n)=nlgn is not polynomially larger than n: no ε>0
+tree: b

j 0
a f n b 
 nd
bound the 2 term with 3 cases (as in the theorem)
such that nlgn=Ω(n1+ε). (lemma 4.3)
We cannot apply the master theorem.  evaluate the sum (asymptotically) using lemma 4.3.
Extend the proof for any n.

7 8

You might also like