Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Lec_5 Recursion II

    Uploaded by

    amrayyad728

    Copyright:

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

    Lec_5 Recursion II

    Uploaded by

    amrayyad728
    12 views20 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    12 views20 pages

    Lec_5 Recursion II

    Uploaded by

    amrayyad728

    Copyright:

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

    CS313

    Dr. Sondos Fadl


     An equation or inequality that describes a function in terms of its
    value on smaller inputs.

    T(n) = T(n-1) + n

     What is the actual running time of the algorithm?

     Need to solve the recurrence


     Find an explicit formula of the expression

     Bound the recurrence by an expression that involves n


     Substitution method

     Tree method

     Master method
    To solve the recurrence equation using substitution method, follow
    these ways:
    1. Iteration
    2. Guessing
    𝑛
    𝑇 𝑛 = 2𝑇 +n
    2
    𝑛 𝑛 𝑛 𝑛
    𝑇 𝑛 = 2 2𝑇 + + n = 4𝑇 + 𝑛 + 𝑛 = 4𝑇 + 2𝑛
    4 2 4 4
    𝑛 𝑛 𝑛
    𝑇 𝑛 = 4 2𝑇 + + 2n = 8T + 3𝑛
    8 4 8
    𝑛
    𝑇 𝑛 = 2𝑤 𝑇 𝑤 + 𝑤𝑛
    2
    𝑇 𝑛 = 2log 𝑛 + 𝑛 log 𝑛
    𝑇 𝑛 = 𝑛log 2 + 𝑛 log 𝑛 = 𝑛 + 𝑛 log 𝑛
    Ο(𝑛 log 𝑛)
    𝑁 𝑁 𝑁 𝑁 𝑁
    𝑇 𝑁 = 2𝑇 + 𝑁 log 𝑁  (1) 𝑇 = 2𝑇 + log
    2 2 4 2 2

    𝑁 𝑁 𝑁
    𝑇 𝑁 = 2× 2𝑇 + log + 𝑁 log 𝑁
    22 2 2

    𝑁 𝑁 𝑁 𝑁 𝑁 𝑁
    𝑇 𝑁 = 4𝑇 + 𝑁 log + 𝑁 log 𝑁  (2) 𝑇 = 2𝑇 + log
    4 2 22 23 22 22

    𝑁 𝑁 𝑁 𝑁
    𝑇 𝑁 =4× 2𝑇 + log + 𝑁 log + 𝑁 log 𝑁
    8 4 4 2

    𝑁 𝑁 𝑁
    𝑇 𝑁 = 8𝑇 + 𝑁 log + 𝑁 log + 𝑁 log 𝑁  (3)
    8 4 2
    𝑤−1
    𝑁 𝑤
    𝑁
    𝑇 𝑁 = 2 𝑇 𝑤 + 𝑁 log 𝑖
    2 2
    𝑖=0
    log2 𝑁 −1
    log2 𝑁
    𝑁
    𝑇 𝑁 = 2 𝑇 1 + 𝑁 log 𝑖
    2
    𝑖=0
    𝟐
    𝚶 𝑵(𝐥𝐨𝐠 𝑵)
    𝑛
    𝑇 𝑛 = 2𝑇 +n
    2
    1. Guess
    2. Prove it (induction tech.)
    3. Prove it at n
     “Cookbook” for solving recurrences of the form:

    n
    T (n)  aT    f (n)
    b
    where, a ≥ 1, b > 1, and f(n) > 0

    𝑛
    𝑇 𝑛 = 𝑎𝑇( )+𝑛𝑑
    𝑏
    Number of recursion non-recursive case
    Input size
     Idea: compare f(n) with 𝑛log𝑏 𝑎

    Case 1:
    If f(n) is dominated by 𝑛log𝑏 𝑎 :  𝑛𝑑 < 𝑛log𝑏 𝑎

    T(n) = (𝑛log𝑏 𝑎 )
     Idea: compare f(n) with 𝑛log𝑏 𝑎

    Case 2:
    If f(n) dominates 𝑛log𝑏 𝑎 :  𝑛𝑑 > 𝑛log𝑏 𝑎

    T(n) = (𝑛𝑑 )
     Idea: compare f(n) with 𝑛log𝑏 𝑎

    Case 3:
    If f(n) = 𝑛log𝑏 𝑎 :  𝑛𝑑 = 𝑛log𝑏 𝑎

    T(n) = (𝑛𝑑 .log 𝑏 𝑛)


    𝑛
    𝑇 𝑛 = 4𝑇 +𝑛
    2
    a
    b
    𝑛log2 4 …. n
    𝑛2 > n

    Θ(𝑛2 )
    𝑛
    𝑇 𝑛 = 4𝑇 + 𝑛2
    2
    a
    b
    𝑛log2 4
    …. 𝑛2

    𝑛2 = 𝑛2

    Θ(𝑛2 . log 2 𝑛)
    𝑛
    𝑇 𝑛 = 4𝑇 + 𝑛3
    2
    a
    b
    𝑛log2 4 …. 𝑛 3

    𝑛2 < 𝑛3

    Θ(𝑛3 )
    𝑛 3
    𝑇 𝑛 = 2𝑇 + 𝑛
    8
    𝑛 1
    𝑇 𝑛 = 2𝑇 + 𝑛3
    8
    1
    𝑛log8 2 …. 𝑛 3
    1 1
    𝑛 =𝑛3 3
    1
    Θ(𝑛3 . log 8 𝑛 )
    =Θ( 𝑛. log 8 𝑛 )
    3
    𝑛
    𝑇 𝑛 = 4𝑇 + 𝑛2 𝑛
    2
    𝑛 1
    𝑇 𝑛 = 4𝑇 2 2
    + 𝑛 .𝑛 𝑛2.5
    2
    𝑛log2 4 …. 𝑛2.5
    𝑛2 < 𝑛2.5
    Θ(𝑛2.5 )
    =Θ(𝑛2 𝑛)
    𝑛
    𝑇 𝑛 = 2𝑇 + 𝑛 log 𝑛
    2
    How?!
    Special Case:
    𝑛
    𝑇 𝑛 = 𝑎𝑇 + 𝑛𝑑 𝑙𝑜𝑔𝑘 𝑛 ,𝐾 > 0
    𝑏

    𝑛log𝑏 𝑎 = 𝑛𝑑

    Θ(𝑛𝑑 . 𝑙𝑜𝑔𝑏 𝑘+1 𝑛)


    𝑛
    𝑇 𝑛 =𝑇 + 𝑛 log 𝑛
    3
    Try the special Case:
    if 𝑛log3 1 = 𝑛1
    𝑛0 <𝑛1

    So, we can't solve this equation by master method


    𝑛
    𝑇 𝑛 = 4𝑇 + 𝑛2 / log 𝑛
    2

    𝑛
    𝑇 𝑛 = 4𝑇 + 𝑛2 .𝑙𝑜𝑔−1 𝑛 𝐾<0
    2

    So, we can't solve this equation by master method

    You might also like