# Asymptotic Question - Determining average case runtime of linear search with summation formula

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).

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources!
– D.W.
Nov 20, 2017 at 6:26
• Let $T$ be the running time. It's a random variable. Can you figure out what the distribution of $T$ is? Can you compute $\mathbb{E}[T]$? It would help if you showed your progress so far and where you got stuck.
– D.W.
Nov 20, 2017 at 6:27
• I think you're misunderstanding the sum. It's not the sum of the elements of the array, but the sum of the number of elements you would need to check to find a result at a given position. Nov 21, 2017 at 20:48

Suppose that it can be any element of your array. You'll have to consider, for $1 <= i <= n$ , what will be the cost if the searched element were at position $i$. If the element were in first position, it would cost $1$ iteration, at second $2$ iterations, and so on. So, if it were at position $i$, it would cost $i$ iterations. In addition, we have $n$ elements, with same chances, so the average cost is the average of the costs that's we have calculated. That's why it's $(1 + 2 + ... + n) / n$.