The Master Theorem applies to recurrences of the form T(n)=aT(n/b)+f(n) for constants a1 and b>1 and gives a solution in the following three cases: Case 1: If f(n)=O(nlogb(a)c) for some constant >0 then T(n)=(nlogb(a)). Case 2: If f(n)=(nlogb(a)logkn) with k0 then T(n)=(nlogb(a)logk+1n). (Note that logkn stands for (logn)k.) Case 3: If f(n)=(nlogb(a)+c) for some constant >0 and if af(n/b)cf(n) for some constant c