The average case occurs in Linear Search Algorithm when :
2015
The average case occurs in Linear Search Algorithm when :
- A.
The item to be searched is in some where middle of the Array
- B.
The item to be searched is not in the array
- C.
The item to be searched is in the last of t he array
- D.
The item to be searched is either in the last or not in the array
Attempted by 225 students.
Show answer & explanation
Correct answer: A
Answer: The average case occurs when the target is equally likely to be at any position in the array (so typically somewhere near the middle).
Key idea: Assume each position is equally likely — then the expected number of comparisons gives the average-case cost.
Let n be the array length. If the target is at position i (1-based), linear search makes i comparisons.
With each position equally likely, the expected number of comparisons is (1/n) * sum of i from 1 to n = (n+1)/2.
Therefore the average number of comparisons is about (n+1)/2, which simplifies to Theta(n).
Conclusion: The average case corresponds to the target being somewhere in the middle (uniformly random position), yielding linear time on average.