---
description: Solutions for Week - 2 Questions
---

# Week - 2

1.  Find the time complexity of the following recurrence relation using forward substitution: $$T(n) = 3T(n-1), n>0$$$$T(0)=1$$\
    $$T(n) = 3 T(n-1)$$\
    Soln:\
    Derive the value of T(n) for values starting from 1

    | n | T(n) |
    | - | ---- |
    | 1 | 3    |
    | 2 | 9    |
    | 3 | 27   |

    \
    Generic equation : $$T(i) = 3^i$$\
    For i=n , $$T(n) = 3^n$$
2.  Solve recurrence $$T(n) = T(n-1) + logn ,  n>0; T(1)=0$$\
    Soln:\
    $$T(n) = T(n-2) + log(n-1) +log(n)$$ $$T(n) = T(n-3) + log(n-2) +log(n-1)+log(n)$$\
    Generic equation\
    $$T(n) = T(n-i) + log(n-i+1) + log(n-i+2) +........log(n)$$\
    Substitute $$n-i = 1$$ (base condition)

    $$i=n-1$$\
    $$T(n)=T(1)+log(0)+log(1) +log(2)+...log(n)$$\
    $$log(0)$$ is ignored\
    $$T(n) = T(1)+log(1.2.3....n)$$

    $$T(n) = 0 + log(n!)$$\
    $$T(n) = nlog(n)$$
3. Use Master theorem to solve the following recurrence relation. (Indicate the case and the solution) For all the cases, consider\
   &#x20;$$T(1) = 1$$      \
   a) $$T(n) = 4T(n/2) + n^{2} , n>1$$\
   Case 2 : $$T(n) = n^{2} log n$$\
   b) $$T(n) = 2^{n} T(n/2) + n^{n}, n>1$$\
   Master's theorem cannot be applied as a is not constant\
   c) $$T(n) = 2T(n/4) + n^{0.51}$$\
   Case 3: $$n^{0.51} > n^{0.50}$$\
   Regularity condition  = $$2.(n/4)^{0.51} <= c.n^{0.51}$$\
   c=(1/2) = 0.5 condition holds\
   d) $$T(n)= 3T(n/3) +(n/2), n>1$$\
   Case 1: $$n logn$$\
   e) $$T(n) = 7 T(n/3) + n^{2}, n>1$$\
   Case 3: $$n^{2}$$\
   Regularity condition  = $$7.(n/3)^{2} <= c.n^{2}$$\
   c=(7/9) = 0.7 condition holds
4. Draw the recursion tree and derive cost for recurrence $$T(n) = a T(n/b) + f(n) , n> 1,  T(1) = 1$$\
   $$T(n) = f(n) + n^{log _{b} a}  + \sum_{i=1}^{log n-1} a^{i} (f(n/b))^{i}$$
5. Can master theorem be used for recurrence relation which takes a poly-logarithmic number of basic operations? \
   &#x20;\[ Extended version of masters theorem ]\
   Yes (Refer to slides in the classroom)

