Improved lower bounds for Shellsort

C. Greg Plaxton, Bjorn Poonen, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
    PublisherIEEE Computer Society
    Pages226-235
    Number of pages10
    ISBN (Electronic)0818629002
    DOIs
    StatePublished - 1992
    Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
    Duration: Oct 24 1992Oct 27 1992

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    Volume1992-October
    ISSN (Print)0272-5428

    Conference

    Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
    Country/TerritoryUnited States
    CityPittsburgh
    Period10/24/9210/27/92

    ASJC Scopus subject areas

    • General Computer Science

    Fingerprint

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

    Cite this