Master theorem

The master theorem provides analysis of Computational complexity for divide-and-conquer Recursive algorithms.

Letting \(T(n)\) denote the total time for the algorithm to process and input of size \(n\), and \(f(n)\) be the time complexity of the top level in the recursion it can be stated \[ T(n) = a \cdot T \left(\frac{n}{b} \right) + f(n) \] where

For example, traversing a binary tress is modelled by \[ T(n) = 2 \cdot T\left(\frac{n}{2}\right) + O(n) \]

As recursive algorithms may be modelled by a tree, its height is \(\log_{b}n\) and at depth \(i\) there are \(a^i\) nodes. This then implies there are \(a^{\log_{b}n} = n^{\log_{b}a}\) leaves and therefore a runtime of \(\Theta(n^{\log_{b}a})\).

Given this, the asymptotic bound \(T(n)\) may the be one of:

  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\), then \(T(n) = \Theta(f(n))\).