Master Theorem the Master Theorem applies to recurrences of

Master Theorem the Master Theorem applies to recurrences of the following form: T(n) aT(n/b) f(n) where a and b 1 are constants and f(m) is an asymptotically positive function. There are 3 cases: 1. If f(n) O(e) for some constant E 0, then T(n) eonleea 2. If f(n) e(nlog, a log n) with k 20, then T(n) e(nogn log n). 3. If f(n) n(nlog. with E >0, and f(n) sassies the regularity condition, then T(n) e(f(n)) Regularity condition: a. S cf(n) for some constant c 1 and all sufficiently large n. The Master Theorem applies to recurrences of the following for T(n) (n/b) +f(n) m: Give an expression for the runtime T(n) if the recurrence can be solved with the Master Theorem. f the Master Theorem doesn\'t apply, simply type in none for both sections Vn Answer: 0 using Case

Solution

In a recurrence of the form:

T(n)=aT(n/b)+O(n^d)

Case 2 of the master theorem applies when we do equal work at every level of the recursion tree. This happens when the amount of work done at the root - O(n^d) - is equal to the amount of work done at the leaves. In other words, when the rate of subproblem proliferation (RSP) is equal to the rate of work shrinkage (RWS) per subproblem:

The RSP is a=3a=3 in your recurrence. This means that, as we move down the tree, we have more subproblems to solve (which is bad news). In particular, at level j, we have 3^j subproblems.

The RWS is b^d=3¹=3 in your recurrence. This means that, as we move down the tree, each subproblem does less and less work (which is good news). In particular, at level j, each subproblem accounts for O(n/3^j) of the total amount of work.

Since a=b^{d ,} the RSP and the RWS cancel out. Thus, it is easy to predict what the running time will be. Since we have a logarithmic number of levels - log(n) - and the total amount of work is the same at every level - O(n) ,then the running time is O(nlog(n)) using Case-2