Tight lower bounds for Shellsort

Mark Allen Weiss, Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


It is proved that the running time of Shellsort using an increment sequence given by Sedgewick is Ω(N 4 3) 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+ε{lunate}/ log N for increment sequences of practical interest and that no increment sequence exists that would make Shellsort optimal.

Original languageAmerican English
Pages (from-to)242-251
Number of pages10
JournalJournal of Algorithms
Issue number2
StatePublished - Jun 1990

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Tight lower bounds for Shellsort'. Together they form a unique fingerprint.

Cite this