Master Theorem

In the previous lessons, we repeatedly used the Divide and Conquer strategy to design efficient algorithms.

However, one important question remains:

How do we mathematically analyze the time complexity of recursive Divide and Conquer algorithms?

This is where the Master Theorem becomes essential.

Why Do We Need the Master Theorem?

Many Divide and Conquer algorithms can be expressed using recurrence relations.

For example:

“How long does Merge Sort take if we split the array into two halves and then merge them?”

Without a systematic method, solving such recurrences can be confusing and error-prone.

The Master Theorem provides a fast and reliable way to determine the time complexity.

General Form of Divide & Conquer Recurrence

Most Divide and Conquer algorithms follow this recurrence pattern:

T(n) = aT(n/b) + f(n)

Each term has a clear meaning.

a represents how many subproblems are created.

n/b is the size of each subproblem.

f(n) is the cost of dividing and combining the results.

Understanding Through a Real Example

Consider Merge Sort.

The array is divided into two halves, so:

a = 2 and b = 2

The merging process takes linear time, so:

f(n) = n

This fits perfectly into the Master Theorem framework.

The Three Master Theorem Cases

The Master Theorem compares f(n) with n^log_ba.

Based on this comparison, we fall into one of three cases.

Case 1 – Subproblem Dominates

If:

f(n) = O(n^{log_ba − ε}) for some ε > 0

Then:

T(n) = Θ(n^log_ba)

This means the recursive calls dominate the total cost.

Case 2 – Balanced Work

If:

f(n) = Θ(n^log_ba)

Then:

T(n) = Θ(n^log_ba log n)

This is the most common case, and it occurs in algorithms like Merge Sort.

Case 3 – Work Outside Recursion Dominates

If:

f(n) = Ω(n^{log_ba + ε}) and regularity conditions hold,

Then:

T(n) = Θ(f(n))

Here, the divide-and-combine work is more expensive than recursion.

Applying Master Theorem – Merge Sort

Let us apply it clearly.

Merge Sort recurrence:

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

Compute:

n^log₂2 = n

Since f(n) = Θ(n), this is Case 2.

Final complexity:

Θ(n log n)

Why Master Theorem Is So Powerful

Instead of expanding recursions step by step, we can directly classify the recurrence and get the answer.

This saves time during exams, interviews, and real-world analysis.

It also helps us compare algorithms at a theoretical level.

Mini Practice

Think carefully:

• Why does Merge Sort always give the same complexity?
• Which part dominates Quick Sort in worst case?

Exercises

Quick Quiz

With the Master Theorem, we now complete the foundation of Divide and Conquer analysis.

In the next lesson, we move into Greedy Algorithms and learn how making locally optimal choices can lead to globally optimal solutions.