Tight lower bounds for Shellsort

Mark Allen Weiss, Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)242-251
Number of pages10
JournalJournal of Algorithms
Volume11
Issue number2
DOIs
StatePublished - Jan 1 1990

All Science Journal Classification (ASJC) codes

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

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

Cite this