What is the average number of comparisons required in sequential search to…
2021
What is the average number of comparisons required in sequential search to find an element?
- A.
n²
- B.
n(n + 1) / 2
- C.
n
- D.
(n + 1) / 2
Attempted by 1350 students.
Show answer & explanation
Correct answer: D
Answer: (n + 1) / 2
Derivation: Assuming the element is present and each position from 1 to n is equally likely, finding the element at position i requires i comparisons.
Average comparisons = (1 + 2 + ... + n) / n
Sum 1 through n = n(n + 1) / 2, so average = [n(n + 1) / 2] / n = (n + 1) / 2.
Notes: n is the worst-case number of comparisons (when the element is last or absent). If the element may be absent with some probability, the expected number of comparisons depends on that probability and will differ from (n + 1)/2.