Answer Happy

How to use MT to solve them?
Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers. (a) T(n) = 4T(n/3) +nlgn (b) T(n) = 3T(n/3)+n/lgn (c) T(n) = 4T(n/2) + n² √n (d) T(n) = 3T(n/3-2) + n/2 (e) T(n) = 2T (n/2) + n/lgn (f) T(n) = T(n/2) +T(n/4) + T(n/8)+n

So, for the Master theorem: T(n) = aT (²) + f(n) where n = size of input a = number of subproblems in the recursion ½ = size of each subproblem. All subproblems are assumed to have the same size. f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solution. Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function. In additional, T(n) has the following asymptotic bounds: Case 1: If f(n) = O(nlogbª-€), then T(n) = O(nloa), where € > 0 is constant Case 2: If f(n) = 0(núa), then T(n) = 0(nlogbª * logn), where € > 0 is constant Case 3: If f(n) = (n²ogª+€), then T(n) = 0f (n), where € > 0 is constant