Q54: Linear search’s recursive equation

Question #54: Which of the following recursive equation holds true for the linear search algorithm?

Options:

1. T(n) = T(n-1) + 1
2. T(n) = T(n/2) + 1
3. T(n) = 2T(n/2) + 1
4. T(n) = T(log(n)) + 1

Solution: In every step while searching linearly, we eliminate one element from the list. Hence the problem T(n) reduces to T(n-1). Therefore, option 1 is correct.