Question

Suppose that L is a sorted list of 1,000,000 elements. To determine whether the x item is in L, the average number of comparisons executed by the sequential search algorithm is _____.

Answer 1

Answer:

≅500,000 comparisons.

Explanation:

The sequential search algorithm is, as its name express, a comparison method to search for a specific value in a list, sorted or not.

It starts with the first element in the list, compares the element with the searched value, if it is a match it stops, otherwise it moves to the next element and repeats.

In general, if the list size is X, the average number of comparisons is:

$\frac{X+1}{2}$

Solving for X=1,000,000, the result is ≅500,000 comparisons.