Lower Bounds for Shellsort

C. Greg Plaxton; Torsten Suel

doi:10.1006/jagm.1996.0825

Lower Bounds for Shellsort

C. Greg Plaxton, Torsten Suel

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

Abstract

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) 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 language	English (US)
Pages (from-to)	221-240
Number of pages	20
Journal	Journal of Algorithms
Volume	23
Issue number	2
DOIs	https://doi.org/10.1006/jagm.1996.0825
State	Published - May 1997

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.1996.0825

Cite this

@article{ba7a0da206fe487b8191b2204efded85,

title = "Lower Bounds for Shellsort",

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

author = "Plaxton, {C. Greg} and Torsten Suel",

note = "Funding Information: * A preliminary version of these results appears in w11x. ²Supported by NSF Research Initiation Award CCR-9111591 and by the Texas Advanced Research Program under Grant 91-003658-480. E-mail: [email protected]. ³Supported by the Texas Advanced Research Program under Grant 91-003658-480 and by an MCD Fellowship of the University of Texas at Austin. E-mail: [email protected].",

year = "1997",

month = may,

doi = "10.1006/jagm.1996.0825",

language = "English (US)",

volume = "23",

pages = "221--240",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Lower Bounds for Shellsort

AU - Plaxton, C. Greg

AU - Suel, Torsten

N1 - Funding Information: * A preliminary version of these results appears in w11x. ²Supported by NSF Research Initiation Award CCR-9111591 and by the Texas Advanced Research Program under Grant 91-003658-480. E-mail: [email protected]. ³Supported by the Texas Advanced Research Program under Grant 91-003658-480 and by an MCD Fellowship of the University of Texas at Austin. E-mail: [email protected].

PY - 1997/5

Y1 - 1997/5

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

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

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

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

U2 - 10.1006/jagm.1996.0825

DO - 10.1006/jagm.1996.0825

M3 - Article

AN - SCOPUS:0040941724

SN - 0196-6774

VL - 23

SP - 221

EP - 240

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Lower Bounds for Shellsort

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this