Suggest edit — recurrence relation

Title

Name

Note

---
title: "recurrence relation"
type: concept
related: [Merge Sort, Master Theorem, Recurrence Relation, Amortized Analysis, Substitution Method]
source: https://www.jemoka.com/posts/kbhrecurrence_relation/
confidence: high
status: active
---

Calculating the runtime of a recursive scheme.
requirements A recursive function \(T\qty(n)\) in terms of \(T\qty(k), k&lt; n\) A base case \(T\qty(1)\) additional information motivation Consider merge sort. It&rsquo;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&rsquo;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&rsquo;s find a closed-form expression for \(T\qty(n)\)!
solving everything master theorem substitution method 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\) &hellip; \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}