A Lower Bound on the Average-Case Complexity of Shellsort
<|reference_start|>A Lower Bound on the Average-Case Complexity of Shellsort: We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p})$ for every $p$. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed.<|reference_end|>
@article{jiang1999a,
    title={A Lower Bound on the Average-Case Complexity of Shellsort},
    author={Tao Jiang (McMaster U.), Ming Li (U. Waterloo), Paul Vitanyi (CWI & U.
  Amsterdam)},
    journal={T. Jiang, M. Li, and P. Vitanyi, A lower bound on the average-case
  complexity of Shellsort, J. Assoc. Comp. Mach., 47:5(2000), 905--91},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9906008},
    primaryClass={cs.CC cs.DS}
}