What is the Big-O time complexity of binary search?

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

Answer: (B)

Binary search cuts the search space in half with every comparison. Start with n elements; after k comparisons, at most n/2^k elements remain possible. To reduce the candidates down to one, you need n/2^k ≤ 1, which means 2^k ≥ n and thus k ≥ log2(n). So the worst-case number of comparisons—and thus the time complexity—grows proportionally to log n. The base of the logarithm doesn’t matter in Big-O terms, since different bases differ only by a constant factor. This is why binary search is not linear (O(n)) and not the heavier O(n log n).