Access Restriction

Author Jiang, Tao ♦ Li, Ming ♦ Vitnyi, Paul
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Kolmogorov complexity ♦ Average-case complexity ♦ Computational complexity ♦ Shellsort ♦ Sorting
Abstract We demonstrate an $Ω(\textit{pn}1+1/\textit{p$ ) lower bound on the average-case running time (uniform distribution) of $\textit{p}-pass$ Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2000-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 47
Issue Number 5
Page Count 7
Starting Page 905
Ending Page 911

Open content in new tab

   Open content in new tab
Source: ACM Digital Library