Average number of comparisons in sorted insertion
-
04-11-2019 - |
Pergunta
The questions is pretty simple: Given a sorted array of N elements, what is the average number of comparisons made in order to add a new element (let's call it x) in its correct position?
I am using linear search for that task.
So far, I've tried to solve it this way:
# of Comparisons Probability of A[i] > x (Not sure if correct)
1 1/n
2 1/n
3 1/n
4 1/n
... ...
n 1/n
Hence, the expected value would be:
$$E[x] = \sum_{x=1}^{n}x \cdot Pr(X=x)$$ $$E[x] = 1 \cdot Pr(X=1) + 2 \cdot Pr(X=2) + 3 \cdot Pr(X=3) + ... + n \cdot Pr(X=n)$$
Using $$Pr(X = n) = \frac{1}{n} $$ for all n,
$$E[x] = \frac{1}{n} \cdot \sum^{n}_{i=1}{i}$$
and finally $$E[x] = \frac{n+1}{2}$$
Still, I'm not sure if this is the correct way to solve it, since I'm not sure about my 1/n assumption.
Any insights would be helpful!
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange