Question

What is the time complexity of Binary Search on a sorted array?

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

Hint:

Any algorithm that works by repeatedly halving the size of the problem (like binary search, or operations on a balanced binary search tree) will typically have a logarithmic time complexity, O(log n).

Answer 1

The Correct Option is C

Binary search is an efficient algorithm for finding an item from a sorted list of items.
It works by repeatedly dividing the search interval in half.
If the value of the search key is less than the item in the middle of the interval, the search is narrowed to the lower half. Otherwise, it is narrowed to the upper half.
This process continues until the value is found or the interval is empty.
At each step, the size of the problem (the search interval) is halved.
If the original array has 'n' elements, after one comparison, the problem size is n/2. After two comparisons, it is n/4, and so on. After 'k' comparisons, the size is $n/2^k$.
The search stops when the size becomes 1. So, we set $n/2^k = 1$, which gives $n = 2^k$.
Solving for k (the number of steps), we get $k = \log_2 n$.
Therefore, the time complexity of binary search is logarithmic, expressed as O(log n).