I am trying to find the average case complexity of the linear search. I know the answer is O(n), but is this correct: The first element has probability $1/n$ and requires 1 comparison; the second probability $1/(n-1)$ and requires 2 comparisons. Hence I have
$1/n + 2/(n-1) +3/(n-2)+ ... + (n-1)/2 + n$
When I work this through it comes out as nlogn.


The $k$the element has probability $1/n$, not $1/(n-k+1)$. For example, for the second element, you need the first element to not be a match, which has probability $(n-1)/n$. Then when you multiply by $1/(n-1)$ for the second element you get $1/n$. So really the complexity is $(1/n)\sum_{k=1}^n k$ which is roughly $n/2$.


As pointed out already by @user2566092, the probability that the search will end at position $k$ is $\frac{1}{n}$ (assuming we are looking for an unique element). This is great if you are looking for exact expected number of comparisons, and is easy enough in this case.

However, in a more complex setting it might be impossible to calculate the exact number. Still, you could perhaps use the following alternate technique.

We know that linear search does not check any element twice, so it is $O(n)$, because expected time cannot be worse than the worst case. If that is all we need, we could stop here. On the other hand, to prove that it is $\Omega(n)$ as well, consider that with probability $\frac{1}{2}$ the element you are searching will be in the second part of the array, hence you will have to preform first at least $\frac{n}{2}$ comparisons. However, this means that the expected number of comparisons is at least $\frac{1}{2}\cdot\frac{n}{2}$ which is already $\Omega(n)$, and so, we get $\Theta(n)$.

I hope this helps $\ddot\smile$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.