GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
143 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.7k points)   | 143 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 (288k 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 Jul 2017
  1. Bikram

    4910 Points

  2. manu00x

    2940 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1506 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. pawan kumarln

    1124 Points

  9. Arnab Bhadra

    1114 Points

  10. Ahwan

    956 Points


24,099 questions
31,074 answers
70,703 comments
29,407 users