Master Theorem

The Master Theorem provides a quick, direct way to calculate the time complexity of divide-and-conquer algorithms. Instead of manually calculating limits or drawing recurrence trees, you can simply extract variables from the equation and apply a set rule.

The Standard Form

The theorem applies to recurrence relations that fit this specific structure:

• $n$: Size of the problem.

• $a$: Number of subproblems in the recursion ($a\ge 1$).

• $b$: Factor by which the subproblem size is reduced ($b>1$).

• $k$: Power of $n$ in the cost of dividing/merging ($k\ge 0$).

• $p$: Power of $\log n$ in the cost of dividing/merging ($p\ge 0$).

The Three Cases

To find the final time complexity, you simply calculate and compare $a$ and bk.

Case 1: Subproblems cost more (Leaves do the most work)

• Condition: a>bk

• Result: T(n)=Θ(nlogb​a)

Case 2: Work is distributed equally across all levels

• Condition: a=bk

• Result: T(n)=Θ(nklogp+1n)

  (Note: If there is no log term originally, $p=0$, making the result simply Θ(nklogn))

Case 3: Dividing/merging costs more (Root does the most work)

• Condition: a<bk

• Result: T(n)=Θ(nklogpn)

 Quick Example: Merge Sort

The recurrence relation for Merge Sort is:

Let’s extract the variables:

• $a=2$ (splits into 2 subproblems)

• $b=2$ (each subproblem is half the size)

• $k=1$ (the work done outside the recursion is n1)

• $p=0$ (there is no $\log n$ term attached to the extra work)

Now, compare $a$ and bk:

• $a=2$

• bk=21=2

• Since a=bk ($2=2$), this triggers Case 2.

Result: T(n)=Θ(n1log0+1n)=Θ(nlogn)