Discrete Mathematics for Computer Science

584 CHAPTER 9 Recurrence Relations

4. (a) Find a recurrence relation to describe the complexity of the recursive code for
   carrying out a linear search of n elements al, a2. an:

INPUT: X E ]R and sequence al1, a2, .... an

OUTPUT: TRUE if x is in the list and FALSE if it is not

recursiveLinearSearch(x, 1, n)

recursiveLinearSearch(x, i, n)

if x = ai then

print TRUE

else

if i = n then

return FALSE

else

recursiveLinearSearch(x, i + 1, n)

(b) Find a closed form for the function found in part (a).

5. Find and solve a recurrence relation that describes the complexity of each of the blocks
   of code shown. The blocks of code evaluate a polynomial at some point. Compare your
   answers to what you found for Exercise 6 in Section 5.6.4

(a)

INPUT: n E M, the coefficients of P stored in a [0.. n], and a real number x0

OUTPUT: P(xo)

Poly = ao

x=1

for/= 1 to n

X = X

Poly = ai -x + Poly

print Poly