-1
$\begingroup$

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

enter image description here

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Oct 11, 2015 at 7:28

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.