0
$\begingroup$

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.

TextBook Answer

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Commented Nov 20, 2017 at 6:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Nov 20, 2017 at 6:27
  • $\begingroup$ 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. $\endgroup$
    – Blckknght
    Commented Nov 21, 2017 at 20:48

1 Answer 1

Reset to default
2
$\begingroup$

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

If you know about probabilities, costs for each element represent a discrete probability distribution, and the average cost is the expected value.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.