A lower bound on the average-case complexity of shellsort

DOI10.1145/355483.355488MaRDI QIDQ2946997zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tao Jiang, Paul M. B. Vitányi, Ming Li

Publication date 19 September 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/9906008

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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(p{n}^{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.

Cited in

(7)

• Average-case analysis of algorithms using Kolmogorov complexity
• Analyzing variants of Shellsort
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• Asymptotic analysis of (3, 2, 1)-shell sort
• The average‐case area of Heilbronn‐type triangles*
• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• Shell sort with expected complexity of O(n _2 n)

This page was built for publication: A lower bound on the average-case complexity of shellsort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946997)