I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2: http://www.hermann-gruber.com/pdf/fun07-final.html
I know the maximum number of inversions in this case is nC2, what i'm struguling with is the probability of two numbers in an iteration being an inversion.
Here is the relevant piece of the paper I'm focusing on, I know the answer to the number of iterations is there, I just can't seem to get to it.
3.2 Comments on optimized variants of bogo-sort
Though optimizing the running time seems somewhat out of place in the field of pessimal algorithm design, it can be quite revealing for beginners in both fields of optimal and pessimal algorithm design to see how a single optimization step can yield a dramatic speed-up. The very first obvious optimization step in all aforementioned algorithms is to swap two elements only if this makes sense. That is, before swapping a pair, we check if it is an inversion: A pair of positions $(i, j)$ in the array $a[1, \dots, n]$ is an inversion if $i < j$ and $a[i] > a[j]$. This leads to optimized variants of bogo-sort and its variations, which we refer to as bogo-sort$_{opt}$, bozo-sort$_{opt}$, and bozo-sort$^+_{opt}$, resp. As there can be at most $\binom{n}{2}$ inversions, this number gives an immediate upper bound on the number of swaps for these variants—compare, e.g., to $\mathcal \Omega(n*n!)$ swaps carried out by bogo-sort. It is not much harder to give a similar upper bound on the expected number of iterations. As the number of comparisons during a single iteration is in $\mathcal O(n)$, we also obtain an upper bound on the expected total number of comparisons:
Lemma 14. The expected number of iterations (resp. comparisons) carried out by the algorithms bogo-sort$_{opt}$, bozo-sort$_{opt}$, and bozo-sort$^+_{opt}$ on a worst-case input $\overline x$ of length $n$ is at most $\mathcal O(n^2\log n)$ (resp. $\mathcal O(n^3\log n)$).