reopened by
22,013 views
71 votes
71 votes

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values:

  1. Choose an $i$ at random from $1..n$
  2. If $A[i] = x$, then Stop else Goto 1;

Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates?

  1. $n$
  2. $n-1$
  3. $2n$
  4. $\frac{n}{2}$
reopened by

11 Answers

8 votes
8 votes

Do not know if it is a correct approach. Some one please verify.
Suppose array contains 10 elements.
'i' will be chosen at random, so probability that we will get our element in first try = 1/10.
Expected number of try for getting the element is  1/p  =   10
https://gateoverflow.in/3561/gate2006-it-22

Hence answer is   a) n .

7 votes
7 votes

This is a type of geometric distribution. Searching an element randomly in array is like tossing a coin(not necessarily fair) until first head comes. Probability of which is 1/n. I am assuming that element is actually in an array. Expected value of geometric random variable is 1/p where p is the probability of success, here 1/n. So answer is 1/(1/n) = n.

Ref. https://en.wikipedia.org/wiki/Geometric_distribution

0 votes
0 votes
All are busy giving proof for this answer let me share what I thought

Now Remember Hashing in that there is concept called open addressing now whether u take linear probe or quadratic probe the no of probe sequence generated are n hence in worst n comparison will be needed and that will be the answer.

I have taken hashing because it is most popular DS for searching

@Arjun Sir plz verify if am thinking In  a right manner
Answer:

Related questions

47 votes
47 votes
7 answers
2
Kathleen asked Sep 15, 2014
17,726 views
The running time of the following algorithmProcedure $A(n)$If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$;is best described by$O(n)$$O(\log ...
35 votes
35 votes
2 answers
4
Kathleen asked Sep 15, 2014
11,772 views
The solution to the recurrence equation $T(2^k) = 3T(2^{k-1})+1, T(1) =1$ is$2^k$$\frac{(3^{k+1}-1)}{2}$$3^{\log_2 k}$$2^{\log_3 k}$