Analysis of Selection Sort

Selection sort loops over indices in the array; for each index, selection sort calls indexOfMinimum and swap. If the length of the array is $n$, there are $n$ indices in the array.

Since each execution of the body of the loop runs two lines of code, you might think that $2n$ lines of code are executed by selection sort. But it's not true! Remember that indexOfMinimum and swap are functions: when either is called, some lines of code are executed.

How many lines of code are executed by a single call to swap? In the usual implementation, it's three lines, so that each call to swap takes constant time.

How many lines of code are executed by a single call to indexOfMinimum? We have to account for the loop inside indexOfMinimum. How many times does this loop execute in a given call to indexOfMinimum? It depends on the size of the subarray that it's iterating over. If the subarray is the whole array (as it is on the first step), the loop body runs $n$ times. If the subarray is of size 6, then the loop body runs 6 times. For example, let's say the whole array is of size 8 and think about how selection sort works.

1. In the first call of indexOfMinimum, it has to look at every value in the array, and so the loop body in indexOfMinimum runs 8 times.
   

2. In the second call of indexOfMinimum, it has to look at every value in the subarray from indices $1$ to $7$, and so the loop body in indexOfMinimum runs 7 times.
   

3. In the third call, it looks at the subarray from indices $2$ to $7$; the loop body runs 6 times.
   

4. In the fourth call, the subarray from indices $3$ to $7$; the loop body runs 5 times.
   

5. …
   

6. In the eighth and final call of indexOfMimimum, the loop body runs just 1 time.

If we total up the number of times the loop body of indexOfMinimum runs, we get 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 times.

Side note: Computing summations from 1 to n

How do you compute the sum $8 + 7 + 6 + 5 + 4 + 3 + 2 + 1$ quickly? Here's a trick. Let's add the numbers in a sneaky order. First, let's add $8 + 1$, the largest and smallest values. We get $9$. Then, let's add $7 + 2$, the second-largest and second-smallest values. Interesting, we get $9$ again. How about $6 + 3$? Also $9$. Finally, $5 + 4$. Once again, $9$! So what do we have?