Consider the following not necessarily best implementation o

Consider the following (not necessarily best) implementation of an algorithm that finds the largest element in an array. function max-element(A) if n = 1 return A[1] val = max-element(A[2. .. n]) if A[1] > val return A[1] else return val Give the best case running time of this algorithm using Theta-notation. Justify your answer. Give a recurrence relation T(n) for the running time of this algorithm in the worst case. Prove that T(n) element of O(n) using the substitution method.

Solution

1)

The if statement will take O(1) time
val = max-element(A[2..n]) will take O(1)
if A[1]>val
return A[1]
else
return val
these statements will take O(1) time.

The best case running time of this algorithm will be O(1).