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