Calculating the runtime of a recursive scheme. requirements A recursive function T\left(n\right) in terms of T\left(k\right), k< n A base case T\left(1\right) additional information motivation Consider merge sort. It’s running time is of shape:

Two submerges, plus the O\left(n\right) merge operation. For the sake of argument clarity (not to mix Big-oh notation and just the recurrence relation), let’s write O\left(n\right) := 11n.

Key task: given a recurrence relation for T\left(n\right), let’s find a closed-form expression for T\left(n\right)! solving everything master theorem substitution method examples example 1 \begin{equation} T_1\left(n\right) = T_1\left(\frac{n}{2}\right) + n, T_{1}\left(1\right) = 1 \end{equation} So each function spawns 1 subproblem, of size \frac{n}{2}. Each subproblem contributes n work. So:

example 2 \begin{equation} T_2\left(n\right) = 4 T_{2}\left(\frac{n}{2}\right) + n, T_2\left(1\right) =1 \end{equation} Each level spawns 4 times the work of the previous layer. layer 1: n = n layer 2: 4 \cdot \frac{n}{2} = 2n Layer 3: 16 \cdot \frac{n}{4} = 4n … \begin{equation} \sum_{i=0}^{\log \left(n\right)} 4^{i} \frac{n}{2^{i}} = n \sum_{i=0}^{\log \left(n\right)} 2^{i} = n\left(2n-1\right) \end{equation}