Author: Stan Eisenstat
Subject: Re: [Cs223] Inversion sort
Date: Wednesday, 04 Mar 2020, 07:10:51

    > Message Posted By: Unknown
    >
    > Hi, I remember that during class, we learned that the number of steps for
    > the lowest number of swaps for inversion sort is
    > (n(n-1)/2)^2 = O(n^4)
    > where we have n(n-1)/2 possible sum of swaps.
    > However, I am not sure how we reach (n(n-1)/2)^2

There are n(n-1)/2 pairs that might form an inversion
that could be reversed.  For each the brute force
approach to counting the reduction in the total number
of inversions looks at each of the n(n-1)/2 pairs to see
if it is no longer an inversion.  That would produce the
expression above.

--Stan-