Search code examples
algorithmdivide-and-conquermaster-theorem

Master theorem cases

My question is about Master theorem. Are there any cases in which a >= 1 and b > 1, but Master theorem does not work? Can you give an example, please?

Solution

  • For the recurrence

    T(n) = 4T(n/2) + n^2 * log n

    None of the three cases applies because there does not exist an e such that log n = Ω(n^e) or log n = O(n^(-e))