My confusion arises when solving the average case. I thought that it would be: 1/n * (number of elements)
But in the solution, they do 1/n * (sum of all the elements). I know that this all goes down to N when in big-o notation but why are they summing all elements of the array and how did they get to just the sum formula? I ended up with the same answer but my thought process was different.
Question: 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 Θ-notation? Justify your answers.
The average should look for (n + 1) / 2 elements
The worst case is n
Assuming equal probability of occurrence 1/n, average number of elements which need to be checked is 1/n * (1 + 2 + ... +n) = (n+1)/2. Running time is Θ(n)
Worst case, the element to search is dead last in the array. In that case n elements need to be searched. Running time is Θ(n)
So all are Θ (n).