Question

Analyze the worst-case, best-case, and average-case number of comparisons of sequential search if exactly three-tenths of the time, the element x to search for is not in the list and if x is in the list, it is equally likely to be in any position.

Answer 1

Worst-case complexity: O(n)

The worst case of sequential search is if either the last element was the target or if the target was not even in the list. Both cases would take nn comparisons, with n being the size of the list in question. Thus the worst case complexity is O(n).

But this assumes the target only appears on the list once/never. In general, it could appear k times. The worst configuration for the target elements to be in is if they are all at the end of the list, in which case we would need n−k+1comparisons to get to the first instance of the target. Giving us a more general worst case complexity of O(n−k)

Best-case performance: O(1)

The best case of sequential search is if the first element of the list is the target. In this case it takes only 1 comparison to return the successful search. Thus the best case complexity is O(1).

Average performance: O(n)

The average case complexity of a search algorithm is the sum of the times it takes to search for each element divided by the number of elements. More formally:

  _n
s1+s2+⋯+s_n    = ∑ S_i

n ⁱ⁼¹ n

Where si is the time it takes to search for the i th element, and n is the length of the list.

  

s1 + s2 +⋯+ n =    n(n+1) .   1 = n+1  

n 2 n 2

In sequential search, we have to perform i comparisons to return i th element. Because of this we can write:

n+1  

k+1

But this assumes the target only appears once on the list. In general, it could appear k times (randomly strewn about) in which case there is a more general average case:

Thus the average case complexity of sequential search is O(n / k) or O(n) if we don't vary k.