CODEWITHSUNDEEP
algorithmmaster-theorem
FoldFence
FoldFence

Reputation: 2802

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.

Upvotes: 3

Views: 3631

Answers (1)

amit
amit

Reputation: 178441

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)

Upvotes: 5

Related Questions