Consider the recurrence T ( n ) = { c if n is 1 T ( ⌊ ( n / 2 ) ⌋ ) + T ( ⌊ ( n / 4 ) ⌋ ) + 4 n , if n is &gt; 1 A. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion treeB. Give a function g(n) and show that it is an upper bound on the sum

Question

Consider the recurrence   T  (  n  )  =      {                            c                                      if                           n                         is 1                                                T          (          ⌊          (          n                      /                    2          )          ⌋          )          +          T          (          ⌊          (          n                      /                    4          )          ⌋          )          +          4          n          ,                                      if                           n                         is &amp;gt; 1                                  A. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion treeB. Give a function g(n) and show that it is an upper bound on the sum

yamalwg · Accepted Answer

Step 1Suppose we start by solving the following recurrence:  T  (  n  )  =  T  (  ⌊  n      /    2  ⌋  )  +  T  (  ⌊  n      /    4  ⌋  )  +  4  nwhere   T  (  1  )  =  c and   T  (  0  )  =  0. .Now let  n  =      ∑          k      =      0              ⌊              log        2            ⁡      n      ⌋            d    k        2    k  be the binary representation of n. We unroll the recursion to obtain an exact formula for   n  ≥  2  T  (  n  )  =  c  [      z          ⌊              log        2            ⁡      n      ⌋        ]      1          1      −      z      −              z        2              +  4      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1        [      z    j    ]      1          1      −      z      −              z        2                  ∑          k      =      j              ⌊              log        2            ⁡      n      ⌋            d    k        2          k      −      j        . .We recognize the generating function of the Fibonacci numbers, so the formula becomes  T  (  n  )  =  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        +  4      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            ∑          k      =      j              ⌊              log        2            ⁡      n      ⌋            d    k        2          k      −      j        . .We now compute lower and upper bounds which are actually attained and cannot be improved upon. For the lower bound consider a one digit followed by a string of zeroes, to give  T  (  n  )  ≥  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        +  4      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            2          ⌊              log        2            ⁡      n      ⌋      −      j          =  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        +  8  ×      2          ⌊              log        2            ⁡      n      ⌋            ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            2          −      j      −      1        . .Now since      |    φ      |    =      |                  1        +                  5                    2        |    &amp;lt;  2the sum term converges to a number, we have      1    2    ≤      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            2          −      j      −      1        &amp;lt;      ∑          j      =      0              ∞            F          j      +      1            2          −      j      −      1        =  2. .For an upper bound consider a string of one digits to get  T  (  n  )  ≤  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        +  4      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            ∑          k      =      j              ⌊              log        2            ⁡      n      ⌋            2          k      −      j          =  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        +  4      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1        (      2          ⌊              log        2            ⁡      n      ⌋      +      1      −      j        −  1  )    =  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        −  4  (      F          ⌊              log        2            ⁡      n      ⌋      +      2        −  1  )  +  4      ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            2          ⌊              log        2            ⁡      n      ⌋      +      1      −      j          =  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        −  4  (      F          ⌊              log        2            ⁡      n      ⌋      +      2        −  1  )  +  4  ×      2          ⌊              log        2            ⁡      n      ⌋      +      1            ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            2          −      j          =  c      F          ⌊              log        2            ⁡      n      ⌋      +      1        −  4  (      F          ⌊              log        2            ⁡      n      ⌋      +      2        −  1  )  +  16  ×      2          ⌊              log        2            ⁡      n      ⌋            ∑          j      =      0              ⌊              log        2            ⁡      n      ⌋      −      1            F          j      +      1            2          −      j      −      1        . .The same constant appears as in the lower bound. Now since the term       F          ⌊              log        2            ⁡      n      ⌋       is asymptotically dominated by       2          ⌊              log        2            ⁡      n      ⌋       (we have       F          ⌊              log        2            ⁡      n      ⌋        ∈  o  (      2          ⌊              log        2            ⁡      n      ⌋        ) because       F          ⌊              log        2            ⁡      n      ⌋        ∈  Θ  (      φ          ⌊              log        2            ⁡      n      ⌋        )  )) joining the upper and the lower bound we get for the asymptotics of this recurrence that it is  T  (  n  )  ∈  Θ      (          2              ⌊                  log          2                ⁡        n        ⌋              )    =  Θ      (          2                                 log          2                ⁡        n              )    =  Θ  (  n  )  , ,which, let it be said, could also have been obtained by inspection.Remark. The evaluation of the constant is done by noting that the generating function of       F          j      +      1            2          −      j      −      1          is              1              /            2              1      −      z              /            2      −              z        2                    /            4      which at   z  =  1 evaluates to             1              /            2              1      −      1              /            2      −      1              /            4        =  2. . We have a certain flexibility as to what power of two to use in the constant but this does not affect the asymptotics.This MSE link has a similar calculation.

William Collins · Accepted Answer

Step 1Inductive Hypothesis:   T  (  k  )  ≤  C  k for   k  &amp;lt;  n for some constant   c  &amp;gt;  0 .Then, prove the inductive step:                    T        (        n        )                            =        T        (        ⌊        (        n                  /                2        )        ⌋        )        +        T        (        ⌊        (        n                  /                4        )        )        +        4        n                                          ≤        T        (        n                  /                2        )        +        T        (        n                  /                4        )        +        4        n                    by monotonicity                                          ≤        C        (        n                  /                2        )        +        C        (        n                  /                4        )        +        4        n                                          =        (        3        C                  /                4        +        4        )        n                                          =        C        n                    ⋆        ⋆            Where   ⋆  ⋆ is true if   (  3  C      /    4  +  4  )  =  C which works when   C  =  16 .So, the moral of the story is that if you can guess that   T  (  n  )  =  O  (  n  ) it is not hard to prove it by induction.EDIT: One final note, it wasn&#039;t asked to get a   Θ bound on T(n), but it is pretty clear (by the recurrence) that   T  (  n  )  =  Ω  (  n  ) since   T  (  n  )  ≥  4  n . Then, combining this with the previous argument shows that   T  (  n  )  =  Θ  (  n  ) .

Answered question

Answer & Explanation

New Questions in Upper Level Math