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) &amp; \text{if n=1} \\ T(n-1)+\Theta(n) &amp; \text{otherwise} \end{cases}
$$

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

So this is my answer.

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?

Thanks for your help.
Why do u need to guess?
T(n) = T(n-1) + cn  {c is a const}
T(n) = T(n-2) +c(n-1) +cn
     = T(n-3) +c*[(n-2)+ (n-1) + n]
..... 

Keep going this way till u reach the arithmetic sequence  (2+...+(n-1)+n]. So, 

T(n) = T(1) + c* n(n-1)/2 = O(n2) 

You may check any Algorithms book or lecture notes on solving recursive equations; we don't usually guess, there r rules and this one is trivial.