I was reading Introduction to algorithms, and stopped at the calculating the running time.

For each $j = 2,3,..,n$ where $n = A.length$, we let $t_j$ denote the number of times the while loop test in line $5$ is executed for that value of $j$ .

so I don't understand this statements with the sums and why the lines 6,7 it takes $t_j-1$

Running time of Insertion Sort


1 Answer 1


Fix a value of $j$, i.e., an iteration of the outer loop. If the condition of the while loop at line 5 is tested $t_j$ times during this iteration (as per definition) then it must be false exactly once. In particular, it must be false in the last of the $t_j$ tests, which causes the inner while loop to terminate.

As a consequence, each instruction in the body of the inner while loop is executed $t_j - 1$ times. Summing the above expression over all considered values of $j$ (from $2$ to $n$) yields $\sum_{i=2}^n (t_j - 1)$.

  • $\begingroup$ ($t_j$ is data dependant with extremes (which?) for ascending and descending input.) $\endgroup$
    – greybeard
    Nov 6, 2021 at 17:10
  • $\begingroup$ ah thanks, so tj will be executed for While-Loop even if it's false but for the statements inside it it will be tj -1 since it won't execute if it's false, right ? and in the calculating the sums can we ignore the first one and just calculate the inner ones since they are more important ? $\endgroup$
    – MR.-c
    Nov 7, 2021 at 11:26

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.