Extended Master's Theorem

This theorem is the extended part of the master’s theorem. If running time in a recurrence equation has a part of log n, then, by this theorem, we can solve the problem.

T(n) = aT(n/b) + n^k*log^pn,

where a ≥ 1, b ≥ 1, k ≥ 0, p is any real number.

(1) If a > b^k, then T(n) = θ(n^log_b^a)

(2) If a = b^k,

-> (a) If p > -1, then T(n) = θ(n^klog^p+1n).

-> (b) If p = -1, then T(n) = θ(n^kloglogn).

-> (c) If p < -1, then T(n) = θ(n^k).

(3) If a < b^k,

-> (a) If p ≥ 0, then T(n) = θ(n^klog^pn).

-> (b) If p < 0, then T(n) = O(n^k).

Questions for solving recurrence problem

Q9 – Find the time complexity of T(n) = T(n/2) + log n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 1, b = 2, k = 0 and p = 1

Now, Case 2 applies because a = b^k

-> a = 1, b^k = 2⁰ = 1

Value of p is 1, means it should be in the case of p > -1.

-> T(n) = θ(n^klog^p+1n).

-> T(n) = θ(n⁰log¹⁺¹n).

-> T(n) = θ(log²n).

You can check the answer by iterative method.

Q10 – Find the time complexity of T(n) = 2T(n/2) + n/log n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 2, b = 2, k = 1 and p = -1

Now, Case 2 applies because a = b^k

-> a = 2, b^k = 2¹ = 2

Value of p is -1, means it should be in the case of p > -1.

-> T(n) = θ(n^kloglogn).

-> T(n) = θ(n¹loglogn).

-> T(n) = θ(n*log²n) = θ(n*logn*logn).

You can check the answer by iterative method.

I will give you some other examples so that you can understand easily.

Example 1 – Find the time complexity of T(n) = 2T(n/2) + n/log² n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 2, b = 2, k = 1 and p = -2

Now, Case 2 applies because a = b^k

-> a = 2, b^k = 2¹ = 2

Value of p is -2, means it should be in the case of p < -1.

-> T(n) = θ(n^k).

-> T(n) = θ(n¹).

Example 2 – Find the time complexity of T(n) = 2T(n/2) + n/log^0.5n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 2, b = 2, k = 1 and p = -0.5

Now, Case 2 applies because a = b^k

-> a = 2, b^k = 2¹ = 2

Value of p is -0.5, means it should be in the case of p > -1.

-> T(n) = θ(n^klog^p+1n).

-> T(n) = θ(n¹log^1-0.5n).

-> T(n) = θ(n*log^0.5n).

Example 3 – Find the time complexity of T(n) = 8T(n/2) + n²log²n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 8, b = 2, k = 2 and p = 2

Now, Case 2 applies because a > b^k

-> a = 8, b^k = 2² = 4

Only one case applies

-> T(n) = θ(n^log_ba).

-> T(n) = θ(n^log₂8).

-> T(n) = θ(n³).

Example 4 – Find the time complexity of T(n) = T(n/2) + n²log²n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 1, b = 2, k = 2 and p = 2

Now, Case 3 applies because a < b^k

-> a = 1, b^k = 2² = 4

Value of p is 2, means it should be in the case of p ≥ 0.

-> T(n) = θ(n^klog^pn).

-> T(n) = θ(n²log²n).

I think you understand the extended master’s theorem very well. But the tricky part is that it can also solve the master’s theorem problem.

Question numbers 6 to 8 can also be solved by the extended master’s theorem.

Q6 – Find the time complexity of T(n) = T(n/2) + n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 1, b = 2, k = 1 and p = 0

Now, Case 3 applies because a < b^k

-> a = 1, b^k = 2¹ = 2

Value of p is 0, means it should be in the case of p ≥ 0.

-> T(n) = θ(n^klog^pn).

-> T(n) = θ(n¹).

Q7 – Find the time complexity of T(n) = 2T(n/2) + 1.

Ans-

Apply Extended master’s theorem.

In this equation, a = 2, b = 2, k = 0 and p = 0

Now, Case 2 applies because a = b^k

-> a = 2, b^k = 2⁰ = 1

Value of p is -1, means it should be in the case of p > -1.

-> T(n) = θ(n^log_ba).

-> T(n) = θ(n¹).

Q8 – Find the time complexity of T(n) = 2T(n/2) + n.

Ans-

Apply Extended master’s theorem.

In this equation, a = 2, b = 2, k = 1 and p = 0

Now, Case 2 applies because a = b^k

-> a = 2, b^k = 2¹ = 2

Value of p is 0, means it should be in the case of p > -1.

-> T(n) = θ(n^klog^p+1n).

-> T(n) = θ(n^*log n).