GATE CS 1996 Q2.13 — Searching, Sorting, Hashing

For a successful sequential (linear) search on $n$ items, the target element must be present in the list. Let us assume that the element is equally likely to be at any of the $n$ positions (uniform probability distribution).

• If the element is at the $1^{\text{st}}$ position, it requires $1$ comparison.
• If the element is at the $2^{\text{nd}}$ position, it requires $2$ comparisons.
• $\dots$
• If the element is at the $i^{\text{th}}$ position, it requires $i$ comparisons.
• If the element is at the $n^{\text{th}}$ position, it requires $n$ comparisons.

Since each position has an equal probability of $\dfrac{1}{n}$, the average (expected) number of key comparisons is given by:

Using the sum of the first $n$ natural numbers, $\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$:

Hence, the correct option is C.