The master theorem

Let \(a \geq 1, b > 1\) be constants, and define \(T(n)\) as such:

\[T(n) = aT(n/b) + f(n),\]

then

  1. If \(f(n) = O(n^{\log_b a - \epsilon})\) for some \(\epsilon > 0\), then \(T(n) = \Theta(n^{\log_b a})\).
  2. If \(f(n) = \Theta(n^{\log_b a})\), then \(T(n) = \Theta(n^{\log_b a} \log n)\).
  3. If \(f(n) = \Omega(n^{\log_b a + \epsilon})\) for some \(\epsilon > 0\), and if \(af(n/b) \leq cf(n)\) for some \(c < 1\) and all sufficiently large \(n\), then \(T(n) = \Theta(f(n))\).

The \(n^\epsilon\) or \(n^{-\epsilon}\) term determines whether \(f\) is polynomially faster/slower than \(n^{\log_b a}\). Note that

  • The 3 cases do not cover all possibilities for \(f\).
  • We do not care whether \(n/b\) is an integer, as replacement with \(\lfloor n/b \rfloor\) or \(\lceil n/b \rceil\) does not affect the asymptotic behaviour.
  • In case 3, the regularity condition “\(af(n/b) \leq cf(n)\) for some \(c<1\) and all sufficiently large \(n\)” is actually sufficient, i.e. it implies \(f(n) = \Omega(n^{\log_b a + \epsilon})\). (Can be proven by induction)

Example

\[T(n) = 2T(n/4) + n \log n\]

We have \(a=2,b=4,f(n)=n\log n\), and \(n^{\log_b a}=n^{\log_4 2}=n^{0.5}\). Since \(f(n) = \Omega(n) = \Omega(n^{0.5+\epsilon})\), we can take \(\epsilon=0.5\). For sufficiently large \(n\), we have that \(af(n/b)=2(n/4)\log(n/4) \leq (n/2)\log(n) = cf(n)\) for \(c=1/2\). Thus by case 3, \(T(n) = \Theta(n\log n)\).

Some intuition?

When we only look at \(f\) defined on exact powers of \(b\), expanding the recurrence we get

\[T(n) = \Theta(n^{log_b a}) + \sum_{j=0}^{\log_b n - 1} a^j f(n/{b^{j}}).\]

The term on the left is the sum of the leaves of the recurrence tree, and the sum term on the right represents the sum of the remaining nodes. Then \(f\) being polynomially faster/slower than \(n^{log_b a}\) determines whether the sum term on the right dominates the big-\(\Theta\) expression.

On the regularity condition in case 3: When you draw the recursion tree, \(af(n/b) \leq cf(n)\) for some \(c<1\) implies that the root node is always greater than the sum of its’ children, i.e. work done at every level decreases by a factor of \(c\). Summing over all the levels, we get an upper bound of something like \(f(n) + cf(n) + c^2 f(n) + ... = f(n)(\frac{1}{1-c})\) (converges since \(c < 1\)). Then \(f(n) = \Omega(n^{\log_b a + \epsilon})\) dominates the big-\(\Theta\) expression.