Question

After performing many sequential searches on a list of 6000 entries, what would you expect to be the average number of times that the target value would have been compared to a list entry? What if the search algorithm was the binary search?

Answer 1

Hello there.

After performing many sequential searches on a list of 6000 entries, what would you expect to be the average number of times that the target value would have been compared to a list entry? What if the search algorithm was the binary search?

3000.

Answer 2

The worst case for searching a list of n entries sequentially is n compares (one for each entry that doesn't match). The best case is 1 compare. Sequential search is thus O(n) complexity. However, ON AVERAGE, n/2 entries have to be examined. The average of the best and worst case (1 and n) is n / 2. The second best and second worst is n / 2, etc. So, the answer is 3000.