Exercise 10.3-4 asked how we might maintain an n-element list compactly in the first n positions of an array. We shall assume that all keys are distinct and that the compact list is also sorted, that is, key[i]

COMPACT-LIST-SEARCH (L, n, k)

If we ignore lines 3-7 of the procedure, we have an ordinary algorithm for searching a sorted linked list, in which index i points to each position of the list in turn. The search terminates once the index i "falls off" the end of the list or once key[i ] ≥ k. In the latter case, if key[i] = k, clearly we have found a key with the value k. If, however, key[i] > k, then we will never find a key with the value k, and so terminating the search was the right thing to do.

Lines 3-7 attempt to skip ahead to a randomly chosen position j. Such a skip benefits us if key[j] is larger than key[i] and no larger than k; in such a case, j marks a position in the list that i would have to reach during an ordinary list search.

Because the list is compact, we know that any choice of j between 1 and n indexes some object in the list rather than a slot on the free list.

Instead of analyzing the performance of COMPACT-LIST-SEARCH directly, we shall analyze a related algorithm, COMPACT-LIST-SEARCH′, which executes two separate loops. This algorithm takes an additional parameter t which determines an upper bound on the number of iterations of the first loop.

COMPACT-LIST-SEARCH′ (L, n, k, t)

To compare the execution of the algorithms COMPACT-LIST-SEARCH (L, n, k) and COMPACT-LIST-SEARCH′ (L, n, k, t), assume that the sequence of integers returned by the calls of RANDOM (1, n) is the same for both algorithms.

a. Suppose that COMPACT-LIST-SEARCH (L, n, k) takes t iterations of the while loop of lines 2-8. Argue that COMPACT-LIST-SEARCH′ (L, n, k, t) returns the same answer and that the total number of iterations of both the for and while loops within COMPACT-LIST-SEARCH′ is at least t .

In the call COMPACT-LIST-SEARCH′ (L, n, k, t), let X_t be the random variable that describes the distance in the linked list (that is, through the chain of next pointers) from position i to the desired key k after t iterations of the for loop of lines 2-7 have occurred.

b. Argue that the expected running time of COMPACT-LIST-SEARCH′ (L, n, k, t) is O(t + E [X_t]).

c. Show that E 

d. Show that

e. Prove that

f. Show that COMPACT-LIST-SEARCH′ (L, n, k, t) runs in O(t + n/t) expected time.

g. Conclude that COMPACT-LIST-SEARCH runs in O(√n) expected time.

h. Why do we assume that all keys are distinct in COMPACT-LIST-SEARCH? Argue that random skips do not necessarily help asymptotically when the list contains repeated key values.