%0 Journal Article %1 incerpi85 %A Incerpi, Janet %A Sedgewick, Robert %D 1985 %I Elsevier %J Journal of Computer and System Sciences %K aks algorithm frobenius shellsort sorting %N 2 %P 210--224 %R 10.1016/0022-0000(85)90042-X %T Improved Upper Bounds on Shellsort %V 31 %X The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N32), due to general results of Pratt. Sedgewick recently gave an O(N43) 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.

@article{incerpi85, abstract = {The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N32), due to general results of Pratt. Sedgewick recently gave an O(N43) 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.}, added-at = {2014-04-20T17:12:29.000+0200}, author = {Incerpi, Janet and Sedgewick, Robert}, biburl = {https://www.bibsonomy.org/bibtex/21e502d764c90672c023270d7eb14878c/ytyoun}, doi = {10.1016/0022-0000(85)90042-X}, interhash = {8dfe665d8c8343a0cc4f00f2d0bd6985}, intrahash = {1e502d764c90672c023270d7eb14878c}, journal = {Journal of Computer and System Sciences}, keywords = {aks algorithm frobenius shellsort sorting}, number = 2, pages = {210--224}, publisher = {Elsevier}, timestamp = {2016-11-08T13:52:57.000+0100}, title = {Improved Upper Bounds on {Shellsort}}, volume = 31, year = 1985 }