algorithms – Inversions of Insertion Sort and Bubble Sort

Let’s consider the swaps performed by insertion sort.
In the $i$-th iteration, insertion sort repeatedly swaps the element $x$ originally in $A(i)$ with some element $y$ originally in $A(1:i-1)$ until the subarray $A(1:i)$ is sorted. Then, since we must have $x<y$ for the swap to occur, we have that each swap induces an inversion in the original array. Notice that the $i$-th iteration takes time proportional to $1+s_i$ where $s_i$ is the number of swaps in the iteration.

If follows that insertion sort takes time $O(n+sum_{i=1}^n s_i) = O(n + s)$, where $s$ is the number of inversions of $A$.
Thus, when insertion sort takes time $Omega(n^2)$ we must have $s=Omega(n^2)$.

Finally, notice that at most one inversion can be removed by each swap performed by bubble sort, implying that bubble sort takes time $Omega(s)=Omega(n^2)$.