@Superku: You got me there, the average case for a linear search is expected to be O(N) and not O(log N). (Sorry, I was thinking of a binary search while writing, which again would also be wrong because it has O(log N) in the worst case instead of O(N)). Sorry!