Average case analysis of linear search

Question

Based on CLRS question 2.2:

Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in $\theta$-notation? Justify your answers.

I have a question regarding the average case.

"assuming that the element being searched for is equally likely to be any element in the array" - what does that exactly mean? Does it mean that the probability for each to happen is $\frac{1}{n}$?

Or could it also be that the element is not in the array at all - is that a case is this probability the same as the rest (and then they are all $\frac{1}{n+1}$)?

Does it matter for the average case how many duplicated are there? Are we assumming that there are no duplicates?

A good explanation about what exactly is the average case would be helpful.

Thanks a lot!!!

Answer 1

The phrase "the element being searched for is equally likely to be any element in the array" is ambiguous. It might mean two different things:

• The element is at a uniformly random position in the array.
• The element is chosen uniformly at random from the set of elements in the array.

This ambiguity suggests that the authors are making the hidden assumption that all elements are distinct, in which case both meanings coincide. Moreover, without this assumption it is impossible to determine the average-case complexity (consider what happens if all elements in the array are identical).

Answer 2

I wouldn't overthink it: With $n$ distinct elements you have a $1/n$ chance of a match. On average you will have to look at $n/2$ elements. That's because $\sum_{i=1}^{n/2} 1/n = 1/2$.

Worst case of course being that you match on the last thing you look at, so have to look at all $n$ of them.