Question

If a linear search is performed on 10 elements, how many comparisons will be needed in worst case?

• A. 1
• B. 10
• C. 9
• D. 11

Hint:

For linear search:
Best-case comparisons = \(1\).
Worst-case comparisons = \(n\).
Average-case comparisons = \(\frac{n+1}{2}\).

Answer 1

The Correct Option is B

Concept:
The efficiency of a search algorithm is measured by the number of key comparisons performed as a function of the input size \(n\).
Linear search checks each element one by one from the first position to the last.

Step 1: Identifying Best, Average, and Worst Cases:
The best-case scenario occurs when the target element is at the first position, needing exactly \(1\) comparison.
The worst-case scenario occurs when the target key is located at the very last position (index \(n-1\)) or is not present in the list at all.

Step 2: Calculation for the Given List Size:
Given the total number of elements: \[ n = 10 \] In the worst-case scenario, the algorithm must compare the search key with every item in the collection: \[ \text{Worst-case comparisons} = n = 10 \] Each of the 10 elements must be evaluated before concluding the search.
Final Answer:
Exactly 10 comparisons will be needed in the worst case. Therefore, option (B) is the correct answer.