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
scroll top