A lower bound on the average-case complexity of shellsort

DOI10.1145/355483.355488zbMATH Open1320.68062DBLPjournals/jacm/JiangLV00arXivcs/9906008OpenAlexW2105465869WikidataQ56113010 ScholiaQ56113010MaRDI QIDQ2946997FDOQ2946997

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)

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.

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)

Cited In (6)

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

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)