Average Time Complexity of Searching An Array Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must also be done, so $\frac{2n}{2} = n$?
It sounds like you're talking about a linear search.  If we assume that the key is equally likely to be in any of the $n$ locations in the array, then the expected location is $\frac{n+1}{2}$.  A linear search for this element would then require $O(\frac{n+1}{2}) = O(n)$ time.