A lower bound on the average-case complexity of shellsort

Authors
Jiang, T Li, M Vitanyi, P
Citation
T. Jiang et al., A lower bound on the average-case complexity of shellsort, J ACM, 47(5), 2000, pp. 905-911
Citations number
13
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF THE ACM → ACNP
Volume
47
Issue
5
Year of publication
2000
Pages
905 - 911
Database
ISI
SICI code
Abstract
We demonstrate an Omega (pn(1+1/p)) lower bound on the average-case running time (uniform distribution) of p-pass Shellsort. This is the first nontriv ial general lower bound for average-case Shellsort.