Question

The worst case time complexity of finding an element using linear search is ______.

• A. O(log n)
• B. O(n)
• C. O(n$^2$)
• D. O(n log n)

Hint:

Worst case means finding the input that forces the algorithm to do the maximum possible amount of work for a list of size $n$. Think about which specific input - a target near the end, or a target that is completely absent - would force linear search to check every single element, then count how that scales with $n$.

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question asks for the worst-case asymptotic time complexity of locating a specific target value in a collection of size $n$ using the Linear Search algorithm.

Step 2: Key Formula or Approach:
- Linear search is a sequential search algorithm that starts at the first element of a list and compares each subsequent element with the target key until a match is found or the end of the list is reached.
- Let $n$ represent the total number of elements in the array or list.

Step 3: Detailed Explanation:
- Let us analyze the best, average, and worst-case scenarios for Linear Search:
- Best Case: The target element is located at the very first index of the list. Here, only 1 comparison is made, yielding a time complexity of $O(1)$.
- Worst Case: The target element is either at the very last index of the list, or it does not exist in the collection at all. In both cases, the algorithm must sequentially compare the target key with every single one of the $n$ elements in the list. This requires $n$ comparisons.
- Since the number of operations in the worst case scales linearly with the input size $n$, the time complexity is expressed asymptotically as $O(n)$.
- Therefore, the worst-case time complexity of linear search is $O(n)$.

Step 4: Final Answer:
The worst-case time complexity of finding an element using linear search is $O(n)$.
Hence, option (B) is the correct choice.