What is the recurrence relation for the linear search recursive algorithm?

Concept: For a recursive algorithm, the running-time recurrence T(n) captures two parts: the constant work done at the current call before recursing (one comparison, one bookkeeping step — call this cost c), plus the time taken by the recursive call on whatever sub-problem remains. In general, T(n) = (work at this level) + T(reduced size).

Application (step by step):

1. Recursive linear search examines exactly one array element per call (e.g. the last element) and compares it with the target — this costs a constant amount of time, c.

2. If it matches, the call returns immediately; otherwise the function makes exactly one recursive call on the remaining n-1 elements (the array with one element removed from consideration).

3. So the total time for input size n equals the constant comparison cost c plus the time for the recursive call on size n-1: T(n) = T(n-1) + c.

4. The base case is T(0) = c (constant, O(1)) when the array is empty.

Cross-check: Solving T(n) = T(n-1) + c by repeated substitution gives T(n) = T(0) + n·c = O(n), matching the well-known linear time complexity of linear search — confirming the recurrence is consistent with the algorithm's known behaviour. This form (reduce-by-one, one recursive call) contrasts with other divide-and-conquer recurrences, shown below: