# 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.

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.

• Sorry, but it's not the mission of this site to check your work. Rather than a command, we'd like a question. Help us to help you: why do you need an independent source to verify your work, except perhaps that you think it's wrong. Here comes the question: why do you think it's wrong? – Rick Decker Apr 17 '20 at 23:25