[O48]

(a) Prove or disprove that there is a number of passes p and an increment sequence such that Shellsort has average-case time complexity O(log n).

(b) Find a better lower bound on average-case time complexity of Shellsort than Theorem 6.6.3 on page 490 (if there is one); give a good or optimal upper bound on average-case time complexity of p-pass Shellsort for the best increment sequences.
Comments. See Exercise 6.6.4 and its comment. Hint for Item (b): perhaps use the methods in [T. Jiang, M. Li and P.M.B. Vit´anyi, J. Assoc.
Comp. Mach. 47:5(2000), 905–911; P.M.B. Vit´anyi Random Struct. Alg., 52:2(2018), 354-363].