Week - 2

Solutions for Week - 2 Questions

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 $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? [ Extended version of masters theorem ] Yes (Refer to slides in the classroom)