Question

Consider the linear search algorithm on an array of size 'n'. What is the worst-case time complexity of linear search?

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

Hint:

The "Best Case" for linear search is $O(1)$, which happens if the target is the very first element. However, we usually design systems based on the "Worst Case" to ensure reliability.

Answer 1

The Correct Option is C

Concept: Time complexity analysis involves determining how the execution time of an algorithm grows as the input size ($n$) increases.
• Linear Search: A process that starts at the first element and compares the target value with every element in the list until a match is found or the list ends.
• Worst-case: The scenario where the algorithm performs the maximum number of steps.

Step 1: Identifying the worst-case scenario.
In a linear search, the worst-case occurs when:
• The target element is at the very last position in the array.
• The target element is not present in the array at all.

Step 2: Counting the operations.
If the array has $n$ elements, the algorithm must perform exactly $n$ comparisons in the scenarios mentioned above.

Step 3: Applying Big O notation.
Since the number of operations is directly proportional to the number of elements $n$, the growth rate is linear. In Big O notation, this is expressed as $O(n)$.