Lower Bounds for Shellsort

C. Greg Plaxton, Torsten Suel

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg2 n)/(lg lg n)2) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.

    Original languageEnglish (US)
    Pages (from-to)221-240
    Number of pages20
    JournalJournal of Algorithms
    Volume23
    Issue number2
    DOIs
    StatePublished - May 1997

    ASJC Scopus subject areas

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

    Fingerprint Dive into the research topics of 'Lower Bounds for Shellsort'. Together they form a unique fingerprint.

    Cite this