In Bubble sort, the number of swaps/comparisons is equal to the number of inversions.
1st pass it will do (n -1) comparison
2nd pass it will do (n-2) comparison….so on
(n-1)n = n^2 – n
Worst case of bubble sort is theta(n^2)
How is the number of inversions theta(n^2) too??
please explain the logic behind this