GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
185 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 (15.4k points)   | 185 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 (294k 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 Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,979 questions
33,554 answers
79,344 comments
31,011 users