2015
On the Average-Case Complexity of Shellsort
Publication
Publication
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 | |
|---|---|
| Cornell University Library | |
| arXiv.org e-Print archive | |
| Organisation | Directie |
|
Vitányi, P. (2015). On the Average-Case Complexity of Shellsort. arXiv.org e-Print archive. Cornell University Library . |
|
