[17] Set h0 = n. Use Theorem 6.6.3 to show that the averagecase time complexity of p-pass Shellsort for the increment sequence

(a) h1 = n1/3 and h2 =1(p = 2) is Ω(n5/3);

(b) h1 = n7/15, h2 = n1/5, and h3 =1(p = 3) is Ω(n23/15), together with the known upper bound O(n23/15) this shows T = Θ(n23/15);

(c) h1 = n1/2, h2 = n1/4, and h3 =1(p = 3) is Ω(n3/2).

Comments. Source:[ P.M.B. Vit´anyi, Ibid.]. Item (a): in [D.E. Knuth [The Art of Computer Programming, Vol. 3: Sorting and Searching, AddisonWesley, 1973, 1998] it is shown that the average-case time-complexity for 2-pass Shellsort is Θ(n5/3). Therefore the lower bound in this item is exact. Item (b): Together with the result of S. Janson and D.E. Knuth

[Random Struct. Alg., 10(1997), 125–142] of an O(n23/15) matching upper bound this shows that the average-case time complexity of 3-pass Shellsort for this increment sequence is Θ(n23/15). Item (c): in the aforementioned Janson-Knuth reference it is conjectured that the increment sequence n1/2, n1/4, 1 gives average-case time complexity O(n3/2) and if this is true then with Item

(c) it is Θ(n3/2).