A recurrence relation that yields

time complexity of recursive algorithm

\begin{equation*} T(n) = a T(n / b) + \mathcal{O}(n^d) = \begin{cases} n^d \log n & a = b^d \\ n^d & a < b^d \\ n^{\log_b a} & a > b^d \end{cases} \end{equation*}

where

• \(a\) is the sub-problem count per recursive call,
• \(n / b\) is the sub-problem size in terms of \(n\)
• \(\mathcal{O}(n^d)\) is the time complexity of the reduction step.

---

• Merge sort example