Analysis of Insert Sort

As a case for study, let us calculate running time for the algorithm INSERTION-SORT. We let tj be the number of times the while loop test at line 1.3 is executed, for that value of j. We also assume that comments are not executable statements, and so they take no time.