2018-03-01
On the average-case complexity of Shellsort
Publication
Publication
Random Structures & Algorithms , Volume 52 - Issue 2 p. 354- 363
We prove a lower bound expressed in the increment se- quence 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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1002/rsa.20737 | |
| Random Structures & Algorithms | |
| Organisation | CWI management |
|
Vitányi, P. (2018). On the average-case complexity of Shellsort. Random Structures & Algorithms, 52(2), 354–363. doi:10.1002/rsa.20737 |
|
