Given a set of n sorted distinct integers, the average case time complexity to…
2026
Given a set of n sorted distinct integers, the average case time complexity to search a key using linear search is
- A.
n/2
- B.
(n-1)/2
- C.
(n+1)/2
- D.
n-1
Attempted by 82 students.
Show answer & explanation
Correct answer: C
In linear search, we examine elements one by one until the key is found. Assuming the key is equally likely to be at any position from 1 to n, we calculate the average number of comparisons. If the key is at index i (where i ranges from 1 to n), it takes exactly i comparisons. The total number of comparisons across all possible positions is the sum 1 + 2 +... + n, which equals n(n+1)/2. To find the average, we divide this total by the number of possible positions (n). Thus, Average = [n(n+1)/2] / n = (n+1)/2. This represents the expected number of comparisons in the average case.",