# Recurrence for the running time of a recursive version of insertion sort

#### WBahn

Joined Mar 31, 2012
25,229
Note that it says "the previous" and not "a previous".

They've omitted the step of generalizing eqn 8 to an expression in terms of T(n-k). Look at eqns 6, 7, 8 and see if you can see the pattern and write it as

T(n) = T(n-k) + ....

Then pick the value of k needed to reduce it to the for of the bottom equation.

#### asilvester635

Joined Jan 26, 2017
73
Last edited by a moderator:

#### WBahn

Joined Mar 31, 2012
25,229
You need to get the equation into the form

T(n) = T(1) + something

You have

T(n) = T(n-constant) + something

What does the constant need to be in order to make the second equation take on the form of the first?

#### asilvester635

Joined Jan 26, 2017
73
When n = 1, the constant needs to be 0 in order to get the equation into the form T(n) = T(1) + something.

Therefore T(1) = T(1-0) + something ----> T(1) = T(1) + something.

#### WBahn

Joined Mar 31, 2012
25,229
The left hand side of the final equation is not T(1), it is T(n).

If the constant is zero, then you have

T(n-0) = T(n) at the spot where you want T(1).

What do you need to subtract from 'n' to get '1'?

#### asilvester635

Joined Jan 26, 2017
73
So we are subtracting some constant 'c' from 'n' to get '1'. What value is 'n' in the first place? Right now it's just a variable, so I'm not sure what constant to pick.

#### WBahn

Joined Mar 31, 2012
25,229
You have

n - something

and you want it to equal 1

So you have

n - something = 1

What does something have to be equal to?