Use Master Theorem to provide running time of the following recurrences, if it can be solved with Master theorem. Otherwise, state that why Master Theorem cannot be applied. 1. T(n) = 2T () + n 2. T(n) = 4T () + n 3. T(n) = 16T (17) + n 4. T(n) = T () -n Problem 4 [Marks = 5] Using iteration method, solve the following recurrences and write the asymptotic time complexity: 1. T(n) = 2T () +n,T(1) = 1 2. T(n) = = T (/2) + 22, T(1) = 1 3. T(n) = T(n 1) + logn, T(0) = 1 4. T(n) = T(n 2) + n, T(0) = 1 5. T(n) = 27 (1) +logn,T(1) = 1