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 a binary search algorithm is O(log n), where "n" is the number of elements in the array. Binary search works by repeatedly dividing the search interval in half, which results in a logarithmic time complexity. It eliminates half of the remaining elements with each step, making it much more efficient than linear search (O(n)).
- O(n) (A) is the time complexity of a linear search, where every element is checked.
- O(n log n) (C) is typical for algorithms that involve both a linear pass through data and a logarithmic operation, such as merge sort.
- O(n²) (D) is the time complexity of algorithms like bubble sort, which involve nested iterations.
Thus, (B) O(log n) is the correct answer for binary search.