Solving the recurrence of recursive insertion sort

Question

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.

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.

Answer 1

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.