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.
Additional Metadata
THEME Null option (theme 11)
Publisher Cornell University Library
Series arXiv.org e-Print archive
Citation
Vitányi, P.M.B. (2015). On the Average-Case Complexity of Shellsort. arXiv.org e-Print archive. Cornell University Library .