Question

Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.

Answer 1

Algorithm
Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers
   if n = 1 return T[0]
   else temp ← Test (T[0..n − 2])

   if temp ≥ T[n − 1] return temp
   else return T[n − 1]

(a)Above Algorithm finds the maximum element in array T[0..n − 1] of real numbers .
(b)Recurrence Relation
   T(n) = T(n-1) + O(1)
solving using substitution method
   T(n) = T(n-1) + 1   -----------------(1)
   T(n-1)= T(n-2) + 1
Putting value of T(n-1) in equation (1), we get
   T(n) = T(n-2) + 1 + 1
similarly,
   T(n) = T(n-3) + 1 + 1 + 1
T(n) = (1 + 1 + 1 +....+ 1) (n times)
T(n) = n
T(n) = O(n)