Question

What happens even if a key is not present in the list during a linear search?

• A. The algorithm stops mid way.
• B. The algorithm skips elements.
• C. The algorithm gives an error.
• D. The algorithm searches through entire list.

Hint:

In an unsorted list of size \(n\), linear search always makes \(n\) comparisons in the worst case (when the item is absent or at the last index).
Never assume early termination unless the list is known to be ordered.

Answer 1

The Correct Option is D

Concept:
Linear search (or sequential search) is a fundamental search technique that makes no assumptions about the order of elements in the list.
It examines every item sequentially from the beginning to find a match with the desired key.

Step 1: Execution Mechanism of Linear Search:
The algorithm begins at index \(0\) and compares each element sequentially with the target key.
If the key matches an element, the search terminates successfully, returning the index.
Because the list is typically unsorted, the algorithm cannot conclude that a key is missing until it has inspected every single element.

Step 2: Analysis of Unsuccessful Search:
When the desired key is not present anywhere in the list, no match will be encountered.
Consequently, the loop continues iterating until it exhausts all \(n\) elements in the list.
It does not stop midway, skip elements, or raise a system error; it simply traverses the complete list before returning a failure flag (such as \(-1\)).
Final Answer:
The algorithm completely inspects the entire list when the search key is absent. Thus, option (D) is correct.