# Insertion Sort running time calculating using summtion

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

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)$$.

• ($t_j$ is data dependant with extremes (which?) for ascending and descending input.) Nov 6, 2021 at 17:10
• 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 ? Nov 7, 2021 at 11:26