Last update: Sat Oct 14 02:35:45 MDT 2017
@Article{Poonen:1993:WCS,
author = "B. Poonen",
title = "The Worst Case in {Shellsort} and Related Algorithms",
journal = j-J-ALG,
volume = "15",
number = "1",
pages = "101--124",
month = jul,
year = "1993",
CODEN = "JOALDV",
DOI = "https://doi.org/10.1006/jagm.1993.1032",
ISSN = "0196-6774 (print), 1090-2678 (electronic)",
ISSN-L = "0196-6774",
bibdate = "Tue Dec 11 09:15:30 MST 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/jalg.bib",
note = "For other Shellsort bounds, see
\cite{Yao:1980:AS,Sedgewick:1986:NUB,Weiss:1990:TLB,Plaxton:1997:LBS,Goodrich:2011:RSS}.",
URL = "http://www.sciencedirect.com/science/article/pii/S0196677483710321",
acknowledgement = ack-nhfb,
fjournal = "Journal of Algorithms",
journal-URL = "http://www.sciencedirect.com/science/journal/01966774",
remark = "The author shows that Shellsort needs at least $N^{1 +
c/\sqrt{m}}$ comparisons in the worst case for $m$
increments, where $c > 0$ is some constant. The author
also shows that $\Omega(N (\log N / \log \log N)^2)$
comparisons are needed, independent of the number of
increments. The result also apply to the Skaker-sort
algorithm.",
}