The Master Theorem
The General Divide and Conquer Recurrence
When we have a Divide and Conquer algorithm that we solve via recursion we can estimate the running time using the General Divide and Conquer Recurrence.
- \(T(n)\) is the total runtime.
- \(n\) is the size of the problem (the number of instances in the input).
- \(a\) is the number of the sub-problems that we create that need to be solved.
- \(b\) is the number of sub-problems we create (we'll mostly see cases where \(a=b=2\)).
- \(f(n)\) is the time spent dividing the problem and later recombining the sub-problems.
Which we combine into this equation.
\[ T(n) = aT \left(\frac{n}{b} \right) + f(n) \]
The Master Theorem
In the case where \(f(n) \in \Theta \left (n^d \right)\) and \(d ≥ 0\) (so it's either 1 or a power of n), we can use the following conditional cases to estimate the runtime.
\[ T(n) \in \begin{cases} \Theta\left (n^d \right ) & \textrm{if }a < b^d \\ \Theta\left (n^d \log n \right ) & \textrm{if }a = b^d \\ \Theta\left (n^{\log_b a} \right) & \textrm{if }a > b^d \end{cases} \]