Question

What is the time complexity of a binary search algorithm on a sorted array?

• A. O(n)
• B. O(log n)
• C. O(n log n)
• D. O(n²)

Hint:

Binary search efficiently narrows down the search space by half each time, leading to a time complexity of O(log n).

Answer 1

The Correct Option is B

The time complexity of binary search is O(log n), with 'n' representing the array's element count. This logarithmic complexity arises from repeatedly halving the search interval, efficiently discarding half of the remaining elements per step, which is superior to linear search's O(n).
- Linear search, which examines each element, has a time complexity of O(n) (A).
- Algorithms combining a linear pass with a logarithmic operation, like merge sort, typically exhibit O(n log n) (C) complexity.
- Algorithms employing nested iterations, such as bubble sort, have a time complexity of O(n²) (D).
Therefore, O(log n), option (B), correctly identifies the time complexity of binary search.