On the average-case complexity of Shellsort
| Authors | |
|---|---|
| Publication date | 03-2018 |
| Journal | Random Structures and Algorithms |
| Volume | Issue number | 52 | 2 |
| Pages (from-to) | 354-363 |
| Number of pages | 10 |
| Organisations |
|
| 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ányi lower bound. We obtain new results, for example, determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1002/rsa.20737 |
| Published at | https://arxiv.org/abs/1501.06461 |
| Other links | https://www.scopus.com/pages/publications/85040798948 |
| Downloads |
1501.06461
(Accepted author manuscript)
|
| Permalink to this page | |