Expected number of iterations for bozo sort opt algorithm

Question

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

Answer 1

The bounds in that paper can be tightened. The tighter bounds in lemma 14 are "..." at most $O(n\log n)$ (resp. $O(n^2\log n))$.

---

As in the question and the papers, we will fix a set of $n$ elements that are totally ordered. The array $a=(a_1, a_2, \cdots, a_n)$ will be a permutation of the $n$ elements. A pair of element $\{a_i, a_j\}$ is a good pair if $i\lt j$ and $a[i]\lt a[j]$. It is a bad pair if $i\lt j$ and $a[i]\gt a[j]$. A bad pair is also call an inversion.

Fact on inversion. Swapping a bad pair strictly decreases the number of all inversions. An array is sorted if and only if the number of all inversions is 0. The maximum number of all inversions is the same as the numbers of all pairs, $\binom n2$.

Now we will use the fact above to show the tightened version of lemma 14 for one case.

The expected number of comparisons carried out by bozo-sort$_{\text{opt}}$ on a worst-case input $x$ of length $n$ is at most $4n^2\log n + (n-1)$, where $\log$ is the natural logarithm.

Proof: Suppose there are $m$ bad pairs in the array. A run of procedure rand. transpose hit one with probability $p = m/n^2$, so the expected number of runs of that procedure until we hit a bad pair is $1/p=n^2/m$. Since the number of bad pairs decreases each time we swap a bad pair, the expected number of runs of that procedure until the array is sorted is bounded by $$\sum_{m=1}^{\binom n2}\frac{n^2}m=n^2\sum_{m=1}^{\binom n2}\frac1m\le 2n^2\log n$$

Note that each procedure rand. transpose makes one comparison. The effect of running procedure sorted before every $n-1$ procedure rand. transpose will at most double number of comparisons besides the initial $n-1$ comparisons. Q.E.D.

_{The above proof is adapted from Fun sort or the chaos of unordered binary search by T. Biedl, T. Chan, E. D. Demaine, R. Fleischer, M. Golin, J.A. King, and J. I. Munro. Discrete Applied Mathematics, 144(3):231–236, 2004.}

Exercises

Exercise 1. Show that $\sum_{m=1}^{\binom n2}\frac1m\le 2\log n.$ (Hint, here is the rate of divergence of harmonic series).

Exercise 2. (One minute or less.) Show that ${m}/\binom n2$ is the probability of procedure rand. transpose in bozo-sort$^+_{\text{opt}}$ hitting one bad pair when there are $m$ bad pairs.

Exercise 3. Show that the expected number of bad pairs found (and, swapped) by a call to procedure randomly permute in bogo-sort$_{\text{opt}}$ when there are $m$ bad pairs is $\Theta(m(n-1)/n^2)$. Show the expected number of total comparisons until the array is sorted is at most by $\Theta(n^2\log n)$.