# Clarification notation in CLRS runtime analysis

I am learning algorithms from the clrs book. I am having trouble understanding the notation the book has placed.

The book wrote the following:

$t_j$ denote the number of times the while loop test in line 5 is executed for that value of $j$."

So does that mean $t_2$ would represent the entire set time the while loop was hit when $j = 2$? • Ad downvoter: while the answer may be obvious to many, this is not a question that can be answered by looking into the book (more), because the notation in the book is the problem. – Raphael Oct 11 '15 at 7:28

## 1 Answer

The number of iterations of the while-loop depends on j which changes during across iterations of the for-loop. Thus, the total runtime of lines 5-7 must depend on $j$, and the runtime of lines 6-7 may depend on $i$ (it does not here).

I can add nothing more over the quote you give; $t_2$ is the number of times line 5 is reached during the for-iteration with $j=2$, indeed.

Our reference question shows you how to obtain such formulae in a structured way. Try to follow the techniques from a blank start and you will see how this comes about.