CORMEN explanation of Insertion Sort Algorithm

Question

I can't understand this particular use of the sigma(summation) notation in the explanation of the Insertion sort of the book Introduction to Algorithms by CLRS:

Let tj denote the number of times the while loop test in line 5 is executed for that value of j.

Can someone explain the use of sigma(summation) in Line 5,6,7? I am aware of the summation formulas and uses.

Answer 1

I think I finally can clearly understand.

The Sigma is expressing that for each j, the while loop may run up to t times. So, when j is equal to 2, the while loop will run t times, when j is equal to 3, the while loop will run t times, but since we don't know if this t, when j=3, is equal to the previous t, when j = 2, we add a subscript to indicate that there are different t's.

The sum runs from 2 to n, and this already represent the for loop that is running in the outer layer.

So, in summary, the limits are from 2 to n, and each time we are in the for loop and we get to the while loop, this while loop will run t times.