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

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top