Improved upper bounds on shellsort

Janet Incerpi, Robert Sedgewick

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N 3 2), due to general results of Pratt. Sedgewick recently gave an O(N 4 3) bound, but extensions of his method to provide better bounds seem to require new results on a classical problem in number theory. In this paper, we use a different approach to achieve O(N1 + ε √1g N) for any ε0.

Original languageEnglish (US)
Pages (from-to)210-224
Number of pages15
JournalJournal of Computer and System Sciences
Volume31
Issue number2
DOIs
StatePublished - Oct 1985

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Improved upper bounds on shellsort'. Together they form a unique fingerprint.

  • Cite this