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?


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.