We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n(lg2n)/(lglgn)2) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.
%0 Journal Article
%1 plaxton97
%A Plaxton, C.Greg
%A Suel, Torsten
%D 1997
%J Journal of Algorithms
%K algorithm shellsort sorting
%N 2
%P 221--240
%R 10.1006/jagm.1996.0825
%T Lower Bounds for Shellsort
%V 23
%X We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n(lg2n)/(lglgn)2) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.
@article{plaxton97,
abstract = {We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n(lg2n)/(lglgn)2) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.},
added-at = {2016-10-29T15:42:37.000+0200},
author = {Plaxton, C.Greg and Suel, Torsten},
biburl = {https://www.bibsonomy.org/bibtex/2dc772c5ae830e8dd6f3d9e68f300db81/ytyoun},
doi = {10.1006/jagm.1996.0825},
interhash = {fb370622da921a807950c7cddbb7a3bd},
intrahash = {dc772c5ae830e8dd6f3d9e68f300db81},
issn = {0196-6774},
journal = {Journal of Algorithms},
keywords = {algorithm shellsort sorting},
number = 2,
pages = {221--240},
timestamp = {2016-10-29T16:38:30.000+0200},
title = {Lower Bounds for {Shellsort}},
volume = 23,
year = 1997
}