On the average‐case complexity of Shellsort

DOI10.1002/RSA.20737zbMATH Open1478.68070arXiv1501.06461OpenAlexW2401070866MaRDI QIDQ4564861

Paul M. B. Vitányi

Publication date: 7 June 2018

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We prove a lower bound expressed in the increment sequence on the average-case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang-Li-Vit'anyi lower bound. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case.

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

zbMATH Keywords

Kolmogorov complexitylower boundaverage-case complexityShellsort

Mathematics Subject Classification ID

Searching and sorting (68P10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

A note on average-case sorting ⋮ On shellsort and the Frobenius problem ⋮ Asymptotic analysis of (3, 2, 1)-shell sort

This page was built for publication: 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 Q4564861)