Search code examples
algorithmrecurrencecomputation

Setting up recurrence relation

I am given this question:

Algorithm Mystery1(A[0...n-1])
//Input: An array A[0...n-1] of n real numbers
if (n = 1) return A[0]
else temp = Mystery1(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 and solve a recurrence relation for the number of times the algorithm’s basic operation is executed.

For part (a) I know that this algorithm computes the smallest element in an array. For part (b), I believe that the basic operation is a comparison, since it will be done the most amount of times, but i can't figure out how to set up the recurrence relation.
I understand how to solve a recurrence relation, i just need help setting up the problem.

Solution

  • The recurrence expression should be:

    T[n] = T[n-1] + O(1)

    Calculating the above expression the time complexity comes out to be O(n).