The recursive version of INSERTION$-$SORT has the following recurrence equation for its time complexity:

$T(n)T(n-1)+(n-1)$

Which case of the Simplified Master Method does this fall in $($and what time complexity does it determine for the algorithm$)?$

Case $3$: Thus $T(n)=O(n)$

Case $1$: Thus $T(n)=O(1)$

Case $2$: Thus $T(n)=O(nlgn)$

The recurrence equation is not the correct one since the non$-$recurrent cost is $n.$

The Simplified Master Theorem does not apply here but it can be shown that $T(n)=O(n^2).$