# Inversions of Insertion Sort and Bubble Sort

An array with bubblesort time $$\Theta(n)$$ is nothing but a sorted array like: A = 1 2 3 4 5
No swaps are done so only $$n - 1$$ comparisons.
An array with insertionsort run time $$\Theta(n^2)$$ is a reverse sorted array: A = 5 4 3 2 1
Each element is swapped in every iteration.
There cannot be any array that can have IS time as $$\Theta(n^2)$$ and BS time as $$\Theta(n)$$.
But how can i prove this in terms of their inversions?

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 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)$$.