88 CHAPTER 1 Sets, Proof Templates, and Induction
(c) A simpler algorithm to calculate 1.00110°0 is to multiply 1000 copies of 1.001
together, using 999 multiplication in all. Using parts (a) and (b), estimate how
many fewer multiplications the FastPower algorithm performs.- Let X and Y be two lists sorted in nondecreasing order. Suppose that for some positive
integer n, there is a combined total of n numbers in the two lists. Prove that X and
Y can be merged into a single list of n numbers in nondecreasing order using at most
n - 1 comparisons. - Prove that the following code to compute Fibonacci numbers is correct:
INPUT: n E N
OUTPUT: Fn
recursiveFibonacci(n)
if n = 0 thenrecursiveFibonacci(O) = 1
else
if n = 1 thenrecursiveFibonacci(1) = 1
else
recursiveFibonacci(n) = recursiveFibonacci(n - 1)
+ recursiveFibonacci(n - 2)- Prove that, at most, n + 1 comparisons are required to determine if a particular number
is in a list of 2n numbers sorted in nondecreasing order. - Prove that exactly n - 1 multiplications are needed to compute the product of n dis-
tinct real numbers in a fully parenthesized expression, regardless of how parentheses
are used.