On The Average-Case Complexity of Shellsort
| Authors | |
|---|---|
| Publication date | 27-01-2015 |
| Edition | 2 |
| Number of pages | 11 |
| Publisher | Ithaca, NY: ArXiv |
| 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\'anyi lower bound. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case. |
| Document type | Working paper |
| Note | Version 1 (2015) and 3 and 4 (2017) also available on ArXiv.org. |
| Language | English |
| Published at | https://arxiv.org/abs/1501.06461v2 |
| Downloads |
1501.06461v2
(Submitted manuscript)
|
| Permalink to this page | |