Question

What is the worst-case time complexity of the Binary Search algorithm?

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

Hint:

To understand Binary Search:
- Requires a sorted array.
- Halves the search space each step (log n).
- Contrast with linear search (O(n)).
- Practice with small sorted arrays.

Answer 1

The Correct Option is C

To determine the worst-case time complexity of the Binary Search algorithm, we need to understand how it operates and analyze its performance.
Step 1: Understand Binary Search
Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half.
It requires the array to be sorted and compares the target value with the middle element, adjusting the search range accordingly.
Step 2: Analyze Option A - O(1)
O(1) represents constant time, which applies to direct access (e.g., array indexing).
Binary Search does not guarantee constant time as it depends on the array size.
Thus, option A is incorrect.
Step 3: Analyze Option B - O(n)
O(n) is typical for linear search, which checks each element sequentially.
Binary Search eliminates half the elements each step, making it more efficient than O(n).
Thus, option B is incorrect.
Step 4: Analyze Option C - O(log n)
In the worst case (e.g., the target is not present or at the last comparison), Binary Search reduces the search space by half with each step.
The number of steps is logarithmic in the size of the array (n), leading to O(log n) complexity.
Thus, option C is correct.
Step 5: Analyze Option D - O($n^2$)
O($n^2$) is associated with algorithms like Bubble Sort, involving nested loops.
Binary Search does not use nested iterations, making this complexity irrelevant.
Thus, option D is incorrect.
Step 6: Conclusion
The worst-case time complexity of Binary Search is O(log n) due to its halving strategy, making option C the answer.