The average number of key comparisons done in a successful sequential search…

In a sequential search, we look for a target element by scanning a list item by item from the beginning until we find a match.

For a successful search, the target element must be present in the list of length n. Assuming that the target element is equally likely to be at any position from 1 to n:

• If the element is at position 1, it takes 1 comparison.

• If the element is at position 2, it takes 2 comparisons.

• If the element is at position 3, it takes 3 comparisons.

• ...

• If the element is at position n, it takes n comparisons.

To find the average number of comparisons, we take the sum of all possible comparisons and divide it by the total number of positions (n):

Average Comparisons = (1 + 2 + 3 + ... + n) / n

Using the standard mathematical formula for the sum of the first n natural numbers, Sum = n * (n + 1) / 2, we substitute it into our equation:

Average Comparisons = [n * (n + 1) / 2] / n = (n + 1) / 2

Therefore, on average, a successful sequential search requires (n + 1) / 2 key comparisons.