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