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

Thread Starter

asilvester635

Joined Jan 26, 2017
73
I understand all the steps of the solution until the very last step (highlighted in yellow). It's not clear to me where we substitute equation (5) into. Click the link for the image.

Pic.png
 
Last edited by a moderator:

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.
 

Thread Starter

asilvester635

Joined Jan 26, 2017
73
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.
Click the image for my response.

20170207_181255000_iOS.jpg
 
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?
 

Thread Starter

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'?
 

Thread Starter

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?
 
Top