How many comparisons does the insertion sort use to sort the lists in question

Question

I have two lists to sort using insertion sort:

1. How many comparisons does the insertion sort use to sort the list $n, n − 1, . . . , 2, 1$?

2. How many comparisons does the insertion sort use to sort the list $1, 2, . . . , n$?

I know that the answer for each respectively is:

1. $1+1+...+1=\sum\limits_{i=1}^{n-1}1=n-1$
2. $\frac{(n^2-n)}{2}$

I don't understand why the first does not have $O(n^2)$ complexity instead of $O(n)$? I guess we need the same amount of comparison for both. I am confused about what the series of numbers in both questions mean?

Insertion Sort Algorithm:

    void insertionSort(int arr[], int n)  
{  
    int i, key, j;  
    for (i = 1; i < n; i++) 
    {  
        key = arr[i];  
        j = i - 1;  
  
        /* Move elements of arr[0..i-1], that are  
        greater than key, to one position ahead  
        of their current position */
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}

Answer 1

It looks like you have a mistake in (1). You wrote: $$1 + 1 + \cdots + 1 = \sum_{i=1}^{n-1} i = (n-1).$$

That sum should have been: $$\sum_{i=1}^{n-1} 1 = n-1.$$

Now in terms of the comparisons, those get made when percolating the element $$A[i]$$ forward. If the elements are already in ascending order, then $$A[i] \geq A[i-1]$$ and no swap is made. So the inner loop does not execute.

Answer 2

When the input sequence is in reverse order, that's the worst case for insertion sort because each new item added to the sorted partition has to sink all the way to the bottom, having to be compared to every other item in the partition. The number of comparisons in this case is given by the good old formula:

$$\frac{n(n - 1)}{2}$$

For instance, 10 items: 45 comparisons. The first item is always inserted with no comparisons. The second item is compared to that one. The next one to those two, and so on. The tenth item is compared to all nine items in the partition. So this is the sum of $0 + 1 + 2 + \ldots + 9 = 45$.

When the input sequence is in order then there are 9 comparisons. The first item is added to the partition without comparison. The second item requires one comparison to conclude it is already higher than the rightmost item, and so on for the remaining items.