A lower bound on the average-case complexity of shellsort

DOI10.1145/355483.355488zbMath1320.68062arXivcs/9906008OpenAlexW2105465869WikidataQ56113010 ScholiaQ56113010MaRDI QIDQ2946997

Paul M. B. Vitányi, Tao Jiang, 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)

Related Items (5)

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

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