6 Recurrences and the Master Theorem

Modified

February 25, 2026

In this section, we learn a rule of thumb for analyzing the runtime of many Divide and Conquer algorithms, i.e. solving their recurrences.

Objectives. After learning this material, you should be able to:

Write the recurrence of a divide-and-conquer algorithm in the form \(T(n) = m T(n/k) + O(n^c)\).
Use the master theorem, given, to conclude the overall running time of the algorithm.

6.1 General D&C framework

We will now see how to analyze the time complexity of divide-and-conquer algorithms in general. We can turn the tree method used above into a general rule-of-thumb that makes analysis much easier, as long as we can write the recurrence for a given D&C algorithm. Many divide-and-conquer algorithms are very similar to the algorithms above, so the general framework looks familiar:

Algorithm 6.1 (Divide-and-Conquer Framework)

divide_and_conquer(L):
   if is_base_case(L):
      return solve_base_case(L)
   (L1,...,Lm) = divide(L)     # each Li has size L/k for some k
   A1 = divide_and_conquer(L1)
   A2 = divide_and_conquer(L2)
   # ...
   Am = divide_and_conquer(Lm)
   return combine(A1,...,Am)

We can see four steps:

Base case stage (lines 2-3): we check if L is a “base case”. For mergesort, the base case was a list of length 0 or 1.
Divide L into k smaller objects (line 4). For mergesort, these were two smaller lists (the first and second halves).
Conquer the objects with recursive calls (lines 6-8). For mergesort, this was sorting the two smaller lists.
Combine the results (line 9). For mergesort, this was calling “merge” on the two smaller lists.

To analyze the time complexity, we want to first write a recurrence, which expresses the runtime \(T(n)\) of the algorithm in terms of itself on smaller inputs.

divide_and_conquer(L):           // T(n) time complexity total
   if is_base_case(L):           // O(1)
      return solve_base_case(L)  // O(1)
   (L1,...,Lm) = divide(L)       // complexity depends on the problem
   A1 = divide_and_conquer(L1)   // T(n/k)
   A2 = divide_and_conquer(L2)   // T(n/k)
   // ...                        // ...
   Am = divide_and_conquer(Lm)   // T(n/k)
   return combine(A1,...,At)     // complexity depends on the problem

We have \(m\) recursive calls, each of which takes \(T(n/k)\) time. Then we have some \(O(1)\) operations for the base case, and finally the time taken by divide() and combine(). if these take time \(O(n^c)\) for some constant \(c \geq 0\), then we get the following general recurrence: \[\begin{align*} T(n) &= m T(n/k) + O(n^c) . \end{align*}\]

In this case, the following theorem gives the solution to the recurrence.

Theorem 6.1 (“Master theorem”) If an algorithm satisfies the recurrence \(T(n) = m T(n/k) + O(n^c)\), then its time complexity is:

\(O(n^c)\) if \(c > \log_k(m)\); or
\(O(n^{\log_k(m)})\) if \(c < \log_k(m)\); or
\(O(n^c \log(n))\) if \(c = \log_k(m)\).

We won’t prove it here (see e.g. Algorithms by Dasgupta, Papadimitriou, and Vazirani), but the proof follows the tree method.

6.1.1 Putting it together

Here is the general approach to analyzing the time complexity of Divide-and-Conquer algorithms:

Write down the recurrence for \(T(n)\):

First check how many recursive calls are made and what the size of the input is for each recursive call. For example, if there are 5 recursive calls and each is on one-third of the original input, then the total work being done is \(5 T(n/3)\).
Then analyze all non-recursive steps and subroutines, specifically divide() and combine(). Let’s suppose the answer is \(O(n^c)\) for some constant \(c\). (Note that \(c=0\) is the case of \(O(1)\), which is the case with binary search.)

Use the master theorem to solve the recurrence. For calculations, remember that \(\log_k(m) = \log(m)/\log(k)\).

Example 6.1 For binary search, the recurrence is \(T(n) = T(n/2) + O(1)\). Here \(m=1\), \(k=2\), and \(c=0\). We have \(\log_k(m) = 0 = c\). So we are in the third case of the master theorem, so the complexity is \(O(n^c \log(n)) = O(\log(n))\).

Example 6.2 For mergesort, the recurrence is \(T(n) = 2T(n/2) + O(n)\). Here \(m=2\), \(k=2\), and \(c=1\). We have \(\log_k(m) = 1 = c\). So we are in the third case again, so the complexity is \(O(n^c \log(n)) = O(n \log(n))\).

Example 6.3 For Karatsuba multiplication, the recurrence is \(T(n) = 3T(n/2) + O(n)\). Here \(m=3\), \(k=2\), and \(c=1\). We have \(\log_k(m) \approx 1.58 > c\). So we are in the second case of the master theorem, so the complexity is \(O(n^{\log_k(m)}) = O(n^{\log_2(3)})\).