(d) Guess the middle of the string, then proceed as in (b). Total effort
required is O(n).
Chapter 13
Section 13.1
2. Using the function subtr in Example 13.3, we get the solution
greater (x, y) = subtr (1, subtr (1, subtr (x, y))).
7.
9. (a)
(b) With the results of part (a) we can use induction to prove the next
identity. Assume that for y = 1, 2,…, n − 1, we have A(2,y) = 2y + 3.
Then
Since