# 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?
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.

Well, that would strongly depend on the algorithm that you use to find out where to insert the new element, and on the distribution of new elements.

Assuming that you do a linear search, and the new element could go to any position with the same probability, your result is close, but not quite exact. The new element can go into one of (n + 1) positions, not n. There may be up to n comparisons needed; n comparisons are needed both if the new element goes into the first array position, and if it goes into the second array position. So the result is

(1 + 2 + 3 + ... + (n-1) + n + n) / (n + 1) =

= (n (n+1) / 2 + n) / (n + 1)

= n (n + 3) / 2 / (n + 1)

= (n + 2 - 2 / (n + 1)) / 2 ≈ (n + 2) / 2,


which is just a tiny bit more than your answer (n + 1) / 2.

• Thanks a lot @gnasher729 ! I completely forgot to mention that I'd perform a linear search in order to find the position to insert the new number!
– woz
Sep 1 '17 at 23:29
• I don't understand what you mean by "n comparisons are needed both if the new element goes into the first array position, and if it goes into the second array position". Why do we need $n$ comparisons in order to insert $x$ into the first position? Assuming I compare by $x < A[i]$, a is single comparison $x < A[0]$ is enough to insert x into the first position. Sep 1 '17 at 23:48
• @fade2black: Because you likely start comparing at the end of the array, which allows you to compare and move one element in the same iteration of the loop. If you start comparing at the beginning, then n comparisons are needed both if the new element is inserted just before, or just after the last element. Sep 2 '17 at 22:38