%0 Journal Article %1 weiss90 %A Weiss, Mark Allen %A Sedgewick, Robert %D 1990 %J Journal of Algorithms %K algorithm shellsort sorting %N 2 %P 242--251 %R 10.1016/0196-6774(90)90005-Y %T Tight Lower Bounds for Shellsort %V 11 %X It is proved that the running time of Shellsort using an increment sequence given by Sedgewick is Ω(N43) which matches the known upper bound. Extending this proof technique to various increment sequences leads to lower bounds that in general always match the known upper bounds. This suggests that Shellsort runs in ω (N1+ϵ/log N for increment sequences of practical interest and that no increment sequence exists that would make Shellsort optimal.

@article{weiss90, abstract = {It is proved that the running time of Shellsort using an increment sequence given by Sedgewick is Ω(N43) which matches the known upper bound. Extending this proof technique to various increment sequences leads to lower bounds that in general always match the known upper bounds. This suggests that Shellsort runs in ω (N1+ϵ/log N for increment sequences of practical interest and that no increment sequence exists that would make Shellsort optimal.}, added-at = {2016-11-08T13:39:11.000+0100}, author = {Weiss, Mark Allen and Sedgewick, Robert}, biburl = {https://www.bibsonomy.org/bibtex/235bd70748c4e8f862759594e7cecbfc9/ytyoun}, doi = {10.1016/0196-6774(90)90005-Y}, interhash = {d86fb5cc924f22987e783b58a65d3bd9}, intrahash = {35bd70748c4e8f862759594e7cecbfc9}, issn = {0196-6774}, journal = {Journal of Algorithms}, keywords = {algorithm shellsort sorting}, number = 2, pages = {242--251}, timestamp = {2016-12-29T04:19:34.000+0100}, title = {Tight Lower Bounds for {Shellsort}}, volume = 11, year = 1990 }