Average-Case Complexity of Shellsort
| dc.creator | Jiang, Tao | |
| dc.creator | Li, Ming | |
| dc.creator | Vitanyi, Paul | |
| dc.date | 1999-01-20 | |
| dc.date.accessioned | 2026-07-07T03:23:54Z | |
| dc.date.available | 2026-07-07T03:23:54Z | |
| dc.description | We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $Ω(pn^{1 + 1/p)$ for all $p \leq \log n$. Using similar arguments, we analyze the average-case complexity of several other sorting algorithms. | |
| dc.description | 11 pages. Submitted to ICALP'99 | |
| dc.identifier | https://arxiv.org/abs/cs/9901010 | |
| dc.identifier | http://arxiv.org/abs/cs/9901010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33128 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2; F.1.3 | |
| dc.title | Average-Case Complexity of Shellsort | |
| dc.type | text |