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.

Answer 2

Concept:

• Worst-case time complexity asks for the maximum number of basic operations an algorithm can ever need, over every possible input of a given size.
• Testing a concrete, specific case first and then generalising the pattern to size $n$ is often clearer than reasoning about best, average and worst cases all at once.

Step 1: Set up a concrete example.
Take an array with $n$ elements, indexed $A[0], A[1], ..., A[n-1]$. Linear search checks $A[0]$ first, then $A[1]$, and so on in order, stopping only when it finds a match.

Step 2: Identify the input that forces the maximum number of checks.
If the target value sits at $A[n-1]$, the very last position, or the target is not present in the array at all, linear search has no way to stop early - it must compare the target against every one of the $n$ elements before it can finish.

Step 3: Count the comparisons for this worst-case input and express it as a function of $n$.
The number of comparisons made is exactly $n$. As $n$ doubles, the number of comparisons doubles too, since every extra element adds exactly one more comparison in this scenario.

Step 4: Confirm by testing the growth rate against the other given options.
For $n = 8$ elements, the worst case needs $8$ comparisons, not $\log_2 8 = 3$ (rules out $O(\log n)$), not $8 \times 3 = 24$ (rules out $O(n \log n)$), and not $8^2 = 64$ (rules out $O(n^2)$). Only direct proportionality to $n$ matches.

Final Answer: $O(n)$