1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – woz Sep 1 '17 at 23:29
  • $\begingroup$ 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. $\endgroup$ – fade2black Sep 1 '17 at 23:48
  • $\begingroup$ @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. $\endgroup$ – gnasher729 Sep 2 '17 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.