[41] Show that the worst-case time complexity of p-pass Shellsort of n items is at least (n log2 n/(log log n)2) for every number p

[41] Show that the worst-case time complexity of p-pass Shellsort of n items is at least Ω(n log2 n/(log log n)2) for every number p of passes and every increment sequence.

Comments. This shows that the best possible average-case time complexity of Shellsort for any number of passes and all increment sequences may be of larger order of magnitude than n log n. Source: [C.G. Plaxton, B.

Poonen, and T. Suel, Proc. 33rd IEEE Symp. Found. Comput. Sci., pp.

226–235, 1992].