Scribd Logo
Upload

Welcome to Scribd!

  • 259 views

    The Master Theorem

    Uploaded by

    NIKHIL SOLOMON P URK19CS1045
    The Master Theorem provides asymptotic bounds for recurrence relations of the form T(n) = aT(n/b) + f(n). There are three cases depending on how f(n) compares to nlogba. Case 1 applies when f(n) is O(nlogba-ε) for some ε > 0, Case 2 when f(n) is Θ(nlogba), and Case 3 when f(n) is Ω(nlogba+ε) and af(n/b) is O(cf(n)) for some c < 1. Examples are provided to illustrate applying the Master Theorem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    The Master Theorem

    Uploaded by

    NIKHIL SOLOMON P URK19CS1045
    259 views11 pages
    The Master Theorem provides asymptotic bounds for recurrence relations of the form T(n) = aT(n/b) + f(n). There are three cases depending on how f(n) compares to nlogba. Case 1 applies when f(n) is O(nlogba-ε) for some ε > 0, Case 2 when f(n) is Θ(nlogba), and Case 3 when f(n) is Ω(nlogba+ε) and af(n/b) is O(cf(n)) for some c < 1. Examples are provided to illustrate applying the Master Theorem.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The Master Theorem provides asymptotic bounds for recurrence relations of the form T(n) = aT(n/b) + f(n). There are three cases depending on how f(n) compares to nlogba. Case 1 applies when f(n) is O(nlogba-ε) for some ε > 0, Case 2 when f(n) is Θ(nlogba), and Case 3 when f(n) is Ω(nlogba+ε) and af(n/b) is O(cf(n)) for some c < 1. Examples are provided to illustrate applying the Master Theorem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    259 views11 pages

    The Master Theorem

    Uploaded by

    NIKHIL SOLOMON P URK19CS1045
    The Master Theorem provides asymptotic bounds for recurrence relations of the form T(n) = aT(n/b) + f(n). There are three cases depending on how f(n) compares to nlogba. Case 1 applies when f(n) is O(nlogba-ε) for some ε > 0, Case 2 when f(n) is Θ(nlogba), and Case 3 when f(n) is Ω(nlogba+ε) and af(n/b) is O(cf(n)) for some c < 1. Examples are provided to illustrate applying the Master Theorem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 11

    The Master Theorem

    Let a>= 1 and b>1 be constants, let f(n) be a function, and let
    T(n) be defined on the non negative integers by the
    recurrence

    T(n) = a T(n/b) + f(n)

    Where we interpret n/b to mean either floor(n/b) or ceil(n/b).


    Then T(n) has the following asymptotic bounds.
    Case 1.
    Case 2
    Case 3
    Examples

    T(n) = 2T(n/2) + n

    a = 2, b = 2, log22 = 1

    Compare nlog22 with f(n) = n

     f(n) = (n)  Case 2

     T(n) = (nlgn)
    5
    Examples
    T(n) = 2T(n/2) + n2
    a = 2, b = 2, log22 = 1

    Compare n with f(n) = n2


     f(n) = (n1+) Case 3  verify regularity cond.
    a f(n/b) ≤ c f(n)
     2 n2/4 ≤ c n2  c = ½ is a solution (c<1)
     T(n) = (n2)
    6
    Examples (cont.)

    T(n) = 2T(n/2) + n

    a = 2, b = 2, log22 = 1

    Compare n with f(n) = n1/2

     f(n) = O(n1-) Case 1

     T(n) = (n)
    7
    Not solvable using Master Theorem
    Examples
    T(n) = 3T(n/4) + nlgn

    a = 3, b = 4, log43 = 0.793

    Compare n0.793 with f(n) = nlgn

    f(n) = (nlog43+) Case 3

    Check regularity condition:

    3(n/4)lg(n/4) ≤ (3/4)nlgn = c f(n), c=3/4

    T(n) = (nlgn) 9
    Examples
    T(n) = 2T(n/2) + nlgn

    a = 2, b = 2, log22 = 1

    • Compare n with f(n) = nlgn


    • seems like case 3 should apply

    • f(n) must be polynomially larger by a factor of n

    • In this case it is only larger by a factor of lgn

    10
     

      
    n 
    logb a
     
    f (n)  O n logb a  

     
       0
    T (n)   n  logb a
    log n  
    f ( n)   n 
    logb a

      c 1
     
     f (n)   
    f (n)   n logb a  AND 
     
     af (n / b)  cf (n) for large n

    You might also like