false, show which of the Master Theorem Cases applies. Show your work for the Case that proves the solution provided or the correct solution. If the Master Theorem cannot be used to show that the solution is true or false show each of the three cases and state that the Master Theorem cannot be used to solve the problem Your answers should be in the format shown on page 74 Second Edition or page 94 Third Edition. Recall that master theorem is as follows: Let a 2 1 and b be constants and f(n) be a function. Let T(n) be defined on the nonnegative integers by the following recurrence T (n)aT(n/b) +f(n) Notice that here n/b can be interpreted as either ln/b or n/b]. Then T(n) can be bounded asymptotically as follows Case 1 Recall, if there exists a constante > 0 such that f(n) = 0(nloga-c) then T(n) = (nloga). Case 2 Recall, if there exists an integer k > 0 such that f(n) = (nlog,alogkn) then T(n) = (nlogsalogk+ln). Note: This formula of Case 2 is more general than Theorem 4.1, and it is given in Erercise 4.4-2 of the Second Edition and in Erercise 4.6-2 of the Third Edition. f(n) is within a polylog factor of nlog. , but not smaller. Polylog is described in Chapter 3 under Logaritmnvely the cost is nlogalgkn at each level and there are (lgn) levels. For a simple case, k = 0 f(n) = (nlogba) T(n)-6( nlogba lg n) Case 3 Recall. if there exists a constant > 0 such that f(n) = (nl gaa+-), and if af(n/b) cf(n) for some constant c