# Solving the recurrence of recursive insertion sort

I have solved that the recurrence of running time of the algorithm given as

$$T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases}$$

So the question is that solve the recurrence that I have solved above.

Case 1

Show that $$T(n) = \Theta(n)$$

Guess $$T(n) \le dn^2$$

$$T(n) \le d(n-1)^2 + cn$$

$$= d(n^2-2n+1)+cn$$

$$= dn^2 - (2d-c)n + d$$

it solves when $$d \ge (2d-c) n$$, which is same as $$\frac{d}{2d-c} \ge n$$

When $$\frac{d}{2d-c} \ge n$$ , then $$T(n) = O(n^2)$$

So this process is equally in Case 2 which is showing $$T(n) = \Omega (n^2)$$.

Can you please check whether my approach is right?