Master Theorem

Divide-and-conquer algorithms follow a generic pattern: they tackle a problem of size $n$ by recursively solving $a$ subproblems of size $\frac{n}{b}$, then combining these answers in $O(n^d)$time for some $a,b,d> 0$.

1. Break a problem into $a$ **subproblems that are smaller instances of the same type of problem.
2. Recursively solve these subproblems.
3. Combine the answer.

This can be captured by the Master Theorem:

<aside> 💡 If $T(n)=aT(\lceil \frac{n}{b}\rceil)+O(n^d)$ for some constants $a >0, b> 1$, and $d\geq 0$, then:

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

</aside>

Figure 1: Given a tree with depth $log_bn$, and branching factor $n$

<aside> 🧾 Given the recurrence relation above, at level $k$, we will have $a^k$ nodes. At the bottom-most level, $\log_b n$, the width of the tree is $a^{\log_bn}$.

Using the change-of-base formula, which states $\log_xy=\frac{\log_z^xy}{\log_zx}$, we can simplify the width of the tree at the base to be $a^k=a^{\log_bn}=a^{(\log_an)(\log_ba)}=n^{\log_ba}$.

At level $k$, we are solving $a$ subproblems in $O(\frac n {b^k}^d)$ time, which simplifies the time in which we do work at level $k$ to:

$$ \text{Complexity}(k)=a^k\cdot O(\frac n {b^k}^d)=O(n^d)\cdot (\frac a {b^d})^k $$

This means that at levels $k=0,\dots,\log_b^n$, this forms a geometric sequence with a ratio of $\frac a {b^d}$.

• If $\frac a {b^d}<1$, the most work is done when $k=0$, $O(n^d)$.
• If $\frac a {b^d}>1$, the most work is done at the base of the tree, $O(n^d\cdot(\frac a {b^d})^{\log_bn})=O(n^d\cdot\frac{a^{\log_bn}}{b^{\log_bn\cdot d}})=O(n^d\cdot\frac{a^{\log_bn}}{n^d})=O(a^{\log_bn})=O(n^{\log_ba})$.
• If $\frac a {b^d}=1$, we are doing a constant amount of $O(n^d)$ work at $\log n$ levels, giving us a time of $O(n^d\log n)$. </aside>

Mergesort Example

You may have previously learnt mergesort takes $O(n \log n)$ time. We can prove this using the Master Theorem.

function merge(x[1...k],y[1...l]):
	if k=0: return y[1...l]
	if l=0: return x[1...k]
	if x[1]<=y[1]:
		return x[1]+merge(x[2...k],y[1...l]
	else:
		return y[1]+merge(x[1...k],y[2...l]This merge procedure does a constant amount of work per recursive call for a total running time of O(k+l). Thus, merges are linear, and the overall time taken by mergesort is T(n)=2T(n/2)+O(n)\\implies O(n\\; log\\; n).

This merge procedure does a constant amount of work per recursive call for a total running time of $O(k+l)$. Thus, merges are linear, and the overall time taken by mergesort is $T(n)=2T(\frac n 2)+O(n)\implies O(n\log n)$.

Matrix Multiplication

The product of two $n\times n$ matrices $X$ and $Y$ is a third $n\times n$ matrix $Z=XY$, with the $(i,j)$-th entry being:

$$ Z_{ij}=\sum_{k=1}^{n}X_{ik}Y_{kj}. $$

In general, matrix multiplication is not commutative: $XY\not=YX$.