Algorithm Analysis of Insertion Sort
Here is a recursive version of insertion sort:

Input: array $A_1,\ldots,A_n$


If $n = 1$, output $A_1$. Otherwise, continue.
Recursively sort $A_1,\ldots,A_{n-1}$ into $B_1,\ldots,B_{n-1}$.
Insert $A_n$ into $B$.
Output $B$.


If we denote by $T(n)$ the running time for arrays of length $n$,
then step 2 takes time $T(n-1)$, whereas step 3 takes time $O(n)$. Combined, we get the recurrence $T(n) = T(n-1) + O(n)$, with base case $T(1) = O(1)$, corresponding to step 1.