1. (a) Use the master theorem given below and provide a tight asymptotic bound for the following recurrence. Show the steps explicitly. Note that logg 4 = 1.26186. T(n) = 47(n/3) + n logan The master theorem The master method depends on the following theorem. Theorem 4.1 (Master theorem) Let a > 1 and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence T(n) =aT(n/b) + f(n). where we interpret n/b to mean either In/b] or [n/b]. Then T(n) has the follow- ing asymptotic bounds: 1. If f(n) = O(n1082-6) for some constant e > 0, then T(n) = (nom). 2. If f(n)=(ns4), then T(n) = (nlos a Ign). 3. If f(n) = 2(no +) for some constant e > 0, and if af (n/b) s cf(n) for some constant c