Use an argument similar to that given in Section 7.9 to prove that log n is a worst-case lower bound for the problem of searching for a given value in a sorted array containing n elements. Perform a...

Use an argument similar to that given in Section 7.9 to prove that log n is a worst-case lower bound for the problem of searching for a given value in a sorted array containing n elements.

Perform a study of Shellsort, using different increments. Compare the version shown in Section 7.3, where each increment is half the previous one, with others. In particular, try implementing “division by 3” where the increments on a list of length n will be n/3, n/9, etc. Do other increment schemes work as well?