First time here? Checkout the FAQ!
+2 votes
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)   | 118 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 (285k 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 May 2017
  1. akash.dinkar12

    3308 Points

  2. pawan kumarln

    1884 Points

  3. Bikram

    1656 Points

  4. sh!va

    1640 Points

  5. Arjun

    1396 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1162 Points

  8. Angkit

    1048 Points

  9. LeenSharma

    1010 Points

  10. Arunav Khare

    754 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    742 Points

  2. pawan kumarln

    510 Points

  3. Arnab Bhadra

    490 Points

  4. bharti

    304 Points

  5. LeenSharma

    248 Points

22,832 questions
29,158 answers
27,673 users