Improved Upper Bounds on Shellsort

The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N3/2), due to general results of Pratt. Sedgewick recently gave an O(N4/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+4/√2lgN).

Authors

• Janet Incerpi
• Robert Sedgewick

Keywords

• Upper bound
• Sorting
• Hydrogen
• Computer science
• Algorithm design and analysis
• Information analysis
• Testing
• Running Time
• Description Of Algorithm
• Number Theory
• Linear Combination
• Practical Standpoint
• Geometric Progression