tj is the number of times the while loop is executed (for the given value of j)
this is a variable that depends on the initial order of the array
Question
For this analysis of Insertion Sort, as shown in Introduction to Algorithms:
What does the summation at line 5 indicate? I'm very confused what tj is supposed to mean. Why does it not just show that it occurs n*n times or something?
Could someone clarify what it is saying?
Solution
tj is the number of times the while loop is executed (for the given value of j)
this is a variable that depends on the initial order of the array
OTHER TIPS
The while loop(iterates i)
is nested inside the for loop(iterates j)
. Hence for every value of j
in the outer loop, the inner loop(i)
iterates for t_j
times.
t_j = (number of times while loop iterates for each j)
. Hence total cost overall would be cost summation for all j
iterations which is sigma{for all j=2..N}(t_j)