GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
97 views
Given an array of 1,000,000 distinct integers you are going to perform 100,000 searches, one at a time, using the linear search algorithm. Each element you are searching for is in the array. What is the expected, total number of comparisons performed by the 100,000 linear searches?

Please explain

Given Ans: 5x10^10 + 5x10^4
asked in Algorithms by Veteran (14.4k points)   | 97 views

1 Answer

+6 votes
Best answer
Expected number of searches for a single linear search of $n$ elements

$$= 1.\frac{1}{n} + 2.\frac{1}{n} + \dots n.\frac{1}{n}$$

as elements are distinct and the probability of any element being equal to the searched element is $\frac{1}{n}$ as element is guaranteed to be present

$= \frac{n+1}{2}$.

Here, $n = 1,000,000$. So, expected number of comparisons $= 1,000,001/2$

Expected no. of comparisons for 100,000 such searches $= 100,000 \times 1,000,001/2 \\=5 \times 10^{10} + 5 \times 10^4$
answered by Veteran (280k points)  
selected by
good question and good explaination ,thanks :)
Top Users Feb 2017
  1. Arjun

    5386 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,021 answers
59,689 comments
22,131 users