Search code examples
algorithmmaster-theorem

Master Theorem with constant

Is this Formula a case 2 from the Master Theorem

T(n) = 2 * T(n/2) + 3

a = 2; b = 2; (f(n) = 3^1) ?

so logba = 1 and c = 1 in this case is it master theorem case 2 ? or should i ignore the constant 3.

Solution

  • This is a case 1 formula, since:

    log_b(a) = 1
f(n) = 3,
3 is in O(1)=O(n^0) -> c = 0 < 1 = log_b(a)

    So, the formula is in Theta(n^(log_b(a)) = Theta(n)

    This is NOT case 2, because case 2 requires f(n)=3 to be in Theta(n^(log_b(a)) = Theta(n), but f(n)=3 is NOT in Theta(n)