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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics