Paper Info
Title
A lower bound on the average-case complexity of shellsort
Abstract
We demonstrate an &Ohgr;(pn1+1/p ) lower bound on the average-case running time (uniform distribution) of p-pass Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.
Year
DOI
Venue
2000
10.1145/355483.355488
J. ACM
Keywords
DocType
Volume
kolmogorov complexity,average-case complexity,computational complexity,shellsort,sorting
Journal
47
Issue
ISSN
Citations 
5
T. Jiang, M. Li, and P. Vitanyi, A lower bound on the average-case complexity of Shellsort, J. Assoc. Comp. Mach., 47:5(2000), 905--91
10
PageRank 
References 
Authors
0.97
10
3
Name
Order
Citations
PageRank
Tao Jiang11809155.32
Ming Li25595829.00
Paul Vitányi32130287.76