Calculating the runtime of a recursive scheme.
requirements
- A recursive function \(T\qty(n)\) in terms of \(T\qty(k), k< n\)
- A base case \(T\qty(1)\)
additional information
motivation
Consider merge sort. It’s running time is of shape:
\begin{equation} T\qty(n) = 2 T\qty(\frac{n}{2}) + O\qty(n) \end{equation}
Two submerges, plus the \(O\qty(n)\) merge operation. For the sake of argument clarity (not to mix Big-oh notation and just the recurrence relation), let’s write \(O\qty(n) := 11n\).
\begin{equation} T\qty(n) = 2 T\qty(\frac{n}{2}) + 11n \end{equation}
Key task: given a recurrence relation for \(T\qty(n)\), let’s find a closed-form expression for \(T\qty(n)\)!
solving everything
examples
example 1
\begin{equation} T_1\qty(n) = T_1\qty(\frac{n}{2}) + n, T_{1}\qty(1) = 1 \end{equation}
So each function spawns 1 subproblem, of size \(\frac{n}{2}\). Each subproblem contributes \(n\) work.
So:
\begin{equation} \sum_{i=0}^{\log n} \frac{n}{2^{i}} = 2n -1 \end{equation}
example 2
\begin{equation} T_2\qty(n) = 4 T_{2}\qty(\frac{n}{2}) + n, T_2\qty(1) =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 \qty(n)} 4^{i} \frac{n}{2^{i}} = n \sum_{i=0}^{\log \qty(n)} 2^{i} = n\qty(2n-1) \end{equation}