Name
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 + ε √1 g N ) for any ε0. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1016/0022-0000(85)90042-X | Journal of Computer and System Sciences |
Keywords | Field | DocType |
improved upper bound,switches,information analysis,algorithm design and analysis,testing,additives,sorting,lead,number theory,computer science,upper bound,hydrogen | Discrete mathematics,Binary logarithm,Combinatorics,Algorithm design,Upper and lower bounds,Sorting,Shellsort,Number theory,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 2 | Journal of Computer and System Sciences |
Citations | PageRank | References |
28 | 10.66 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Janet Incerpi | 1 | 52 | 21.82 |
| Robert Sedgewick | 2 | 1723 | 544.99 |