Register

GATE CSE 2002 | Question: 2.10

• reopened by
22,333 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
User Avatar

11 Answers

0 votes
0 votes
-->>FOR THOSE WHO HAS GONE THROUGH PROBABILITY SYLLABUS , THIS IS A STANDARD CASE OF 'EXPECTED VALUE" IN "GEOMETRIC DISTRIBUTION".

-->>Expected value for geometric distribution is 1/p. Where p is probability of success.

-->> So answer would be = 1/(1/n) = n.
User Avatar
0 votes
0 votes
The expected number of comparisons made by the algorithm before it terminates is n. This is because each comparison has an equal probability of 1/n of finding the given number x and thus, the expected number of comparisons is equal to the total number of comparisons (n).
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

47 votes
47 votes
7 answers
2
Kathleen asked Sep 15, 2014
17,938 views
GATE CSE 2002 | Question: 2.11
The running time of the following algorithm Procedure $A(n)$ If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$; is best described by $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$
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 ...
User Avatar
35 votes
35 votes
2 answers
4
Kathleen asked Sep 15, 2014
11,968 views
GATE CSE 2002 | Question: 1.3
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}$
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}$
User Avatar
Link Copied!