On The Average-Case Complexity of Shellsort
Preprint
Abstract
We prove a lower bound expressed in the increment sequence on the average-case complexity (number of inversions which is proportional to the running time) of Shellsort. This lower bound is sharp in every case where it could be checked. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A lower bound on the average-case complexity of shellsortJournal of the ACM, 2000
- Short Note: Empirical study of the expected running time of ShellsortThe Computer Journal, 1991
- Improved upper bounds on shellsortJournal of Computer and System Sciences, 1985
- An analysis of (h, k, 1)-ShellsortJournal of Algorithms, 1980
- Three approaches to the quantitative definition of information*International Journal of Computer Mathematics, 1968
- An empirical study of minimal storage sortingCommunications of the ACM, 1963
- A high-speed sorting procedureCommunications of the ACM, 1959