229 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?

Given Ans: 5x10^10 + 5x10^4
asked | 229 views

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 (327k points)
selected
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 :)

+1 vote