GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
114 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.6k points)   | 114 views

1 Answer

+7 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 (283k points)  
selected by
good question and good explaination ,thanks :)
@Arjun Sir, after seeing the question,my approach was like:

For 1st search, the number of comparisons would be O(n).

For 2nd search, the number of comparisons will be O(n-1) since now, 1 element has been decreased from the array.

Similarly, the searches would continue in the form of O(n)+O(n-1)+O(n-2)+O(n-3)+........+1=O(n^2).

So, for 100,000 searches, Total comparisons= (n^2)*100,000

Given, n=1000,000, so, Total Comparisons= 100,000 *100,000 *100000=10^15.

Kindly guide me where am I going wrong since this is not the answer. :(
@Bongbirdie, the question does not mention that once an element is found in the array, it is removed from it. So even after x number of searches are performed, the array still has 1,000,000 entries. Even if you keep track of the indices at which your search succeeded, to skip those indices in subsequent searches, you have to make a comparison anyway. For example, suppose the first search succeeded at index 200 and you remember this fact for performing the second search. Now while performing the second search, if you decide that I will skip the index 200, then each index has to be compared to 200 to decide whether or not to skip it. So instead of reducing the number of comparisons, you end up increasing it.

For the above two reasons, the number of possible comparison counts does not decrease in consecutive iterations of the linear search.

Hope this helps :)


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arunav Khare

    1464 Points

  10. Arjun

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,062 answers
63,294 comments
24,160 users