3 ms·
Shellsort is not O(n log n) but not O(n^2) either
I thought I recalled Knuth showing shellsort was better than O(n^2), but worse than O(n log n). According to this page, shellsort is somewhere around N(log N)^2 and N^(1.25). The proof is in Knuth, TAOCP.
- pmiller2 17y agoI thought I recalled Knuth showing shellsort was better than O(n^2), but worse than O(n log n). According to this page, shellsort is somewhere around N(log N)^2 and N^(1.25). The proof is in Knuth, TAOCP.
- pmiller2 17y agoProof of O (n (log n)^2) at: http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/sh...