Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Recurrences Slides

    Uploaded by

    Iván Eduardo
    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.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Recurrences Slides

    Uploaded by

    Iván Eduardo
    28 views2 pages
    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.

    Original Title

    Recurrences-slides

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    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.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    28 views2 pages

    Recurrences Slides

    Uploaded by

    Iván Eduardo
    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.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    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