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 - http://www.scopus.com/inward/record.url?scp=0020828334&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0020828334&partnerID=8YFLogxK
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 -