Tight lower bounds for Shellsort

Mark Allen Weiss; Robert Sedgewick

doi:10.1016/0196-6774(90)90005-Y

Tight lower bounds for Shellsort

Mark Allen Weiss, Robert Sedgewick

Computer Science

Research output: Contribution to journal › Article › peer-review

6 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 ω (N^1+ε{lunate}/ log N for increment sequences of practical interest and that no increment sequence exists that would make Shellsort optimal.

Original language	English (US)
Pages (from-to)	242-251
Number of pages	10
Journal	Journal of Algorithms
Volume	11
Issue number	2
DOIs	https://doi.org/10.1016/0196-6774(90)90005-Y
State	Published - Jun 1990

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(90)90005-Y

Cite this

@article{1943ad97d0294c5fab49b5b32e7d0681,

title = "Tight lower bounds for Shellsort",

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.",

author = "Weiss, {Mark Allen} and Robert Sedgewick",

note = "Funding Information: by National Science Foundation Grant DCR-8605962.",

year = "1990",

month = jun,

doi = "10.1016/0196-6774(90)90005-Y",

language = "English (US)",

volume = "11",

pages = "242--251",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Tight lower bounds for Shellsort

AU - Weiss, Mark Allen

AU - Sedgewick, Robert

N1 - Funding Information: by National Science Foundation Grant DCR-8605962.

PY - 1990/6

Y1 - 1990/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38249018654&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249018654&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(90)90005-Y

DO - 10.1016/0196-6774(90)90005-Y

M3 - Article

AN - SCOPUS:38249018654

SN - 0196-6774

VL - 11

SP - 242

EP - 251

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Tight lower bounds for Shellsort

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this