TY - GEN
T1 - Improved lower bounds for Shellsort
AU - Plaxton, C. Greg
AU - Poonen, Bjorn
AU - Suel, Torsten
N1 - Publisher Copyright:
© 1992 IEEE.
PY - 1992
Y1 - 1992
N2 - The authors give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In particular, they hold for nonmonotone increment sequences and adaptive Shellsort algorithms, as well as for some recently proposed variations of Shellsort.
AB - The authors give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In particular, they hold for nonmonotone increment sequences and adaptive Shellsort algorithms, as well as for some recently proposed variations of Shellsort.
UR - http://www.scopus.com/inward/record.url?scp=1542500279&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1542500279&partnerID=8YFLogxK
U2 - 10.1109/SFCS.1992.267769
DO - 10.1109/SFCS.1992.267769
M3 - Conference contribution
AN - SCOPUS:1542500279
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 226
EP - 235
BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PB - IEEE Computer Society
T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
Y2 - 24 October 1992 through 27 October 1992
ER -