Finding running time

[Sophia]

Hi guys,


I have a problem with finding the running time of insertion sort. the following calculation is what I read in CLRS book but I don't understand why it used 'n' as 'times' in for loop, but then it used 'sigma tj'(j from 2 to n) in while loop, while 'tj' denotes the number of times the while loop test in line 5 is executed for that value of j. Here is the insertion sort I'm talking about :

http://tinypic.com/view.php?pic=25jffc6&s=5

Any help would really be appreciated.

Sophia

[Dmitry Cherkassov]

The times column says how many times the line will be executed.
And # of executions of line 5 depends on value of j

line 5 is executed at most:

1 time for j = 2
2 times for j = 3
3 times for j = 4
...
n-1 times for j = n

summing over j gives you that sigma.

so the "while" head in line 5 will be executed \sigma_{j=2}^n{t_j}
times

[Sophia]

Thanks Dmitry.
So the sigma is because of the sum over j?
And if we have another loop instead of 'while' for example a 'for' loop again, we would have the same thing again? I mean any loop inside of the first loop will be like the way you describe it and cause a sigma because of the iteration of 'j'?

[Dmitry Cherkassov]

> So the sigma is because of the sum over j?

Use the right words. Sigma is just a denotation of summ operator.
Roughly speaking, yes.

> And if we have another loop instead of 'while' for example a 'for'
> loop again, we would have the same thing again? I mean any loop inside
> of the first loop will be like the way you describe it and cause a
> sigma because of the iteration of 'j'?

it's not important whether it's while or for loop. What is important
is
that if # steps of inner loop steps depends on specific iteration of
outer loop. That's what makes things little hadrer.
Sometimes walking through an algorithm with specified input does
help.

[Sophia]

Thanks for your help, I understood completely :)