2 Added linear search from comment, deleted tag

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!

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?

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!

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!

1

Average number of comparisons in sorted insertion

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?

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!