what is the expected number of comparisons made before the algorithm terminates ?

Question

Comments

Is 3 answer?

---

I am getting 2.5 :/

---

can it not be done by this https://gateoverflow.in/840/gate2002-2-10 ?

---

No , that's a diff ques.

---

https://gateoverflow.in/71322/go2017-algorithm-4

---

it should be $6$

Answer 1

let X be a random variable denoting number of comparisons made by the algorithm before terminates.

total number of permutations possible using the numbers present in the array = $\frac{5!}{2!}$ = 60(as x presents 2 times.and assume that other numbers are not repeated)

so, p(X=1)=$\frac{4!}{60}$=$\frac{24}{60}$

p(X=2)=$\frac{3*1*3!}{60}$=$\frac{18}{60}$

p(X=3)=$\frac{3*2*1*2!}{60}$=$\frac{12}{60}$

p(X=4)=$\frac{3!*1}{60}$=$\frac{6}{60}$

so expected no of comparisons=1*$\frac{24}{60}$+2*$\frac{18}{60}$+3*$\frac{12}{60}$+4*$\frac{6}{60}$

                                                        =2

Comments

I think the approach should be like this :

We need to find the expected number of comparisons E(x). E(x)= 1*P(x=1) + 2*P(x=2)...

Here '1' is the number of comparisons and P(x=1) should be the probability that the item is found at 1st attempt (i.e. 1 comparison) . Not in the 1st index.

P(x=2) should the the probability that the item is found at 2nd attempt not in the 2nd attempt.

---

       MiNiPanda  read the ques first.it said that sequential search is being done here.

---

Oh yes.. I overlooked it and assumed it to be random.. thanks

Answer 2

In the worst case , it will require Atmost 4 comparisons to as x is present 2 times already in the worst case it will be at (n-1)th and nth position int the array !!