Exercises 2.3-7

Solution 1: Sort the set first. For any element y in S, use binary search to determine whether there is one element z in S-y such that y + z = x. Since the binary search can be done Θ(lg n), the overall running time is Θ(n lgn).

Solution 2: Sort the set first. Let be the sorted result. If > x, then the solution must be in . If < x, then the solution must be in . If = x, we are done. So we can solve the problem recursively. The overall running time is Θ(n lgn).

Exercises 2.3-6

No. Although the comparisons are Θ(n lgn), but the data movements are still .

Exercises 2.3-5

Worst case running time.
T(1) = 1
T(n) = T(n/2) + 1
T(n) = lg n.

Exercises 2.3-4

Worst case running time.
T(1) = 1
T(n) = T(n-1) + n
T(n) =

Exercises 2.3-3

Base case: n = 2, T(n) = 2.
Induction step: Assume that T(n) = n lg n for all n = , c < k. Then for n = . T(n) = = = n lg n.

Exercises 2.3-2

Eliminate step 8 and 9.
For step 12~17, add the condition that and .

Exercises 2.3-1