What is the recurrence relation for the linear search recursive algorithm?
T(n-2)+c
2T(n-1)+c
T(n-1)+c
T(n+1)+c
View Answer
Correct Answer: C — T(n-1)+c
Explanation:
After each call in the recursive algorithm, the size of n is reduced by 1. Therefore the optimal solution is T(n-1)+c.
