Search code examples
algorithmmaster-theoremclrs

Master Theorem: comparing two versions of the theorem

I have generally seen two versions of the Master theorem.

Version 1:

(from Tim Roughgarden's course)

for recurrence relations of the form,

T(n) <= aT(n/b)+O(n^d)
where a >= 1, b > 1, and d >= 0

there are 3 cases,

case 1: if a=b^d, then T(n) = O(n^dlog(n))
case 2: if a<b^d, then T(n) = O(n^d)
case 3: if a>b^d, then T(n) = O(n^logb(a))

Version 2:

(from CLRS)

for recurrence relations of the form,

T(n) = aT(n/b)+f(n)
where a>=1 and b>1 (both constants)

there are 3 cases:

case 1: if f(n) = O(n^logb(a-ε) for some ε > 0, then T(n) = Θ(n^logb(a))
case 2: if f(n) = Θ(n^logb(a)), then T(n) = Θ(logn*n^logb(a))
case 3: if f(n) = Ω(n^logb(a+ε)) for some ε > 0, and if af(n/b)<=cf(n) for some 
constant c<1 and all sufficiently large n,then T(n) = Θ(f(n))

Question: Which version should one favor and why?

Solution

  • Second version because it does not have a constrain on f(n).

    As you see, in the first version your f(n) can be only in a specific form, the second case f(n) is any function, so you can solve recurrences like T(n) = 2 T(n/2) + nlog(n) + n^2 * sin(n)