Improved upper bounds on shellsort

Janet Incerpi; Robert Sedgewick

doi:10.1016/0022-0000(85)90042-X

Improved upper bounds on shellsort

Janet Incerpi
, Robert Sedgewick

Computer Science

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

28 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(N^{1 + ε √1g N}) for any ε0.

Original language	English (US)
Pages (from-to)	210-224
Number of pages	15
Journal	Journal of Computer and System Sciences
Volume	31
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(85)90042-X
State	Published - Oct 1985

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/0022-0000(85)90042-X

Cite this

@article{d80a10156d904e5ca78cf81480f2de9f,

title = "Improved upper bounds on shellsort",

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

author = "Janet Incerpi and Robert Sedgewick",

note = "Funding Information: * This research was supported in part by NSF Grant MCS83XI8806 and in part by the Office of Naval Research and DARPA under Contract N0001483-K-O146 and ARPA Order 4786. t Current address: INRIA, Sophia Antipolis, 06560 Valbonne, France. f Current address: Dept. of Computer Science, Princeton University, Princeton, N.J. 08544.",

year = "1985",

month = oct,

doi = "10.1016/0022-0000(85)90042-X",

language = "English (US)",

volume = "31",

pages = "210--224",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Improved upper bounds on shellsort

AU - Incerpi, Janet

AU - Sedgewick, Robert

N1 - Funding Information: * This research was supported in part by NSF Grant MCS83XI8806 and in part by the Office of Naval Research and DARPA under Contract N0001483-K-O146 and ARPA Order 4786. t Current address: INRIA, Sophia Antipolis, 06560 Valbonne, France. f Current address: Dept. of Computer Science, Princeton University, Princeton, N.J. 08544.

PY - 1985/10

Y1 - 1985/10

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

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

UR - https://www.scopus.com/pages/publications/0020828334

UR - https://www.scopus.com/pages/publications/0020828334#tab=citedBy

U2 - 10.1016/0022-0000(85)90042-X

DO - 10.1016/0022-0000(85)90042-X

M3 - Article

AN - SCOPUS:0020828334

SN - 0022-0000

VL - 31

SP - 210

EP - 224

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Improved upper bounds on shellsort

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this