Short Note: Empirical study of the expected running time of Shellsort
Open Access
- 1 January 1991
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 34 (1) , 88-91
- https://doi.org/10.1093/comjnl/34.1.88
Abstract
We present the results of a large empirical study of the running time of Shellsort. A previous study reported by Knuth for several increment sequences gave running times between Θ(N1.25) and Θ(NN1.28) or Θ(Nlog2N). but these forms are not very accurate especially for large permutations. Our results given a running time of Θ(N5/4) for all of the increment sequences suggested by Knuth and Θ(N7/6) for an increment sequence suggested by Sedgewick. Our fits are accurate to within 1% for 250 ≤NN. Much of the error in the fits appears to be related to the error in the measured data. These results are significant because they suggest that O(log N) increment sequences with Θ(Nk) worst-case running times have Θ(N(k+1)/2) average-case running times and that there is no increment sequence for which Shellsort is O(Nlog N), even on average.Keywords
This publication has 0 references indexed in Scilit: