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

algorithmscomputational complexitycomputer sciencediscrete mathematicssorting

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;  
    }  
}

Best Answer

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.

Related Question