4. Consider the following recursive algorithm.

ALGORITHM Q(n)

//Input: A positive integer

if n = 1 return 1

else return Q(n-1) + 2 *n-1/nb. Set up a recurrence relation for the number of multiplications made by this

algorithm and solve it.

c. Set up a recurrence relation for the number of additions/subtractions made

by this algorithm and solve it./n9. Consider the following recursive algorithm.

ALGORITHM Riddle(A[0..n-1])

//Input: An array A[0..n-1] of real numbers

if n = 1 return A[0]

else temp← Riddle(A[0..n -2])

if temp ≤ A[n 1] return temp

else return A[n - 1]

a. What does this algorithm compute?

b. Set up a recurrence relation for the algorithm's basic operation count and

solve it.