Discussion

The average number of key comparisons done in a successful sequential search in a list of length n is

Answer: D

The average is \((n+1)/2\).

If the key is equally likely to be at any of the n positions, finding it at position i takes i comparisons, so the average is

\[ \begin{aligned} \frac{1 + 2 + \cdots + n}{n} &= \frac{n(n+1)/2}{n} \\ &= \frac{n+1}{2} \end{aligned} \]

n/2 and (n - 1)/2 are off by a half or one, and log n is the cost of binary search, not sequential search.

In the worst case, when the key is last or absent, sequential search makes n comparisons.

No comment is present. Be the first to comment.

Loading…