设置递归关系

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) 这个算法计算了什么？
(b) 建立并求解算法基本运算次数的递推关系 被执行。

对于 (a) 部分，我知道该算法计算数组中的最小元素。对于(b)部分，我认为基本操作是比较，因为它会被执行的次数最多，但我不知道如何建立递归关系。
我了解如何解决递归关系，我只需要帮助设置问题。

Answer 1

递归表达式应该是：

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

计算上面的表达式，时间复杂度为O(n)。