[40] Prove Theorem 6.6.3.

Comments. Source: [P.M.B. Vit´anyi, Ibid.]. Hint: The proof uses the fact that most permutations of n keys have high Kolmogorov complexity.

Since the number of inversions in the Shellsort process is not easily amenable to analysis, a simpler process is analyzed. The lower bound on the number of moves of this simpler process gives a lower bound on the number of inversions of the original process. Find the simpler process and show that the largest number of unit moves of each key in the kth pass of the simpler process is less than hk−1/hk where h1,...,hp is the increment sequence and h0 = n. Subsequently show using the high Kolmogorov complexity of the permutation that most keys in each pass have a number of moves close to the maximum. This gives a lower bound on the total number of moves of the simpler process and hence a lower bound on the number of inversions of the original process. This holds for the chosen single permutation. Since all permutations but for a vanishing fraction (with growing n) have this high Kolmogorov complexity, the lower bound on the total number of inversions holds for the averagecase of the original Shellsort process. The lower bound coincides with all known bounds for the average-case time complexity as mentioned in the main text.