3 ms·
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)^
by pmiller2 17y ago
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.