1. a. What is the running time of Shellsort using the two-increment sequence {1, 2}?
b. Show that for any N, there exists a three-increment sequence such that Shellsort runs in O(N5/3) time.
c. Show that for any N, there exists a six-increment sequence such that Shellsort runs in O(N3/2) time.
2. a. Prove that the running time of Shellsort is 0.(N2) using increments of the form 1, c, c2, ... , ci for any integer c.
b. Prove that for these increments, the average running time is 8(N3/2).
3. Prove that if a k-sorted ?le is then h-sorted, it remains k-sorted.
4. Prove that the running time of Shellsort, using the increment sequence suggested by Hibbard, is 0.(N3/2) in the worst case. (Hint: You can prove the bound by con- sidering the special case of what Shellsort does when all elements are either 0 or 1.)
Set a[i] = 1 if i is expressible as a linear combination of ht, ht-1, ... , hLt/2J+1 and 0 otherwise.
5. Determine the running time of Shellsort for
a. sorted input
b. reverse-ordered input