Average-case complexity of linear search where half of the elements in the array are duplicates
-
05-11-2019 - |
Pergunta
I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:
A(n) = $\frac{n + 1}{2}$
However, I am having trouble coming up with the Average Case complexity in the case where half of the elements in the size n array are duplicates. Take, for example, this array of integers:
1 2 6 6 5 4 6 6 6 3
Here is my thought-process so far:
I know that if we are looking for a specific element x in the array, the probability of doing it in a certain number of comparisons is $\frac{1}{n}$, since the distribution is uniform. So the average number of comparisons is still $\frac{n + 1}{2}$. (referencing this question's approved answer)
If the element we are looking for x is the duplicate number, however, then what is that probability of doing it in a certain number of comparisons? From there, how would I then compute the average-case complexity?
Nenhuma solução correta