Masters Theorem (122A)

Shortcut version

For a recurrence relation of the form:

\begin{aligned}
T(n) &= aT\left(\left\lceil\dfrac nb\right\rceil\right) + O(n^d)\\

a, b \in \Z&; a > 0, b> 1\\
d\in\R&; d\geq 0    
\end{aligned}

we have this shortcut

T(n) = \begin{cases}
    O(n^d) & \text{if }d > \log_ba\\
    O(n^d\log n) & \text{if } d = \log_b a\\
    O(n^{\log_ba})&{if }d < \log_ba
\end{cases}

This is a shortcut because a lot of the times we get polynomial runtimes for the work at each level O(n^d). For a more general Masters theorem, see the next section.

General version

For a runtime function T(n) given by:

T(n)=a\cdot T\left(\frac nb\right) + f(n)

where a, b, n\in \Bbb N and they represent:

a: number of recursive calls. a > 0
b: how much we reduce the problem. b>1
f(n) : work at each level.

Example

T(n)=3T\left(\dfrac n4\right) + n^2\\

In this case a = 3, b=4, f(n)=n^2. It means the main routine does 3 recursive calls, each with a problem size \frac n4, and the work at each level is n^2.

We have 3 cases depending on n^{\log_ba} vs. f(n)

Case 1. The recursive step is slow (lots of recursive calls)

First check if:

n^{\log_ba} >\,f(n)

If that’s true, then check if:

f(n)=O\left(n^{(\log_ba) - \varepsilon}\right)\text{ for some }\varepsilon>0

If such \varepsilon exists, then:

T(n)=\Theta(n^{\log_ba})

@Hint Observe that n^{\log_ba} is the depth of the recurrence tree. So the overall T(n) is dominated by the recursion (a lot of leaves, not much work at each leaf)

Case 2. Recursion and \small f(n) are about the same speed

First check if:

f(n) = \Theta(n^{\log_ba})

If that’s true, then:

T(n)=\Theta(n^{\log_ba}\cdot \log n)

Case 3. The work at each level is slow

First check if:

n^{\log_ba} <\,O(f(n))

Then check if:

There exists \varepsilon > 0 such that:

 f(n)=\Omega \left(n^{(\log_ba)+\varepsilon}\right)

AND if there exists positive c<1 such that:

 a\cdot f\left(\frac nb\right)\le c\cdot f(n)

If both are satisfied, then:

T(n)=\Theta(f(n))

All the big O, \Omega, \Theta checks can be done using the limit lemma.