Linear search average-case complexity? 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$.
