The worst-case time complexity of binary search on a sorted array of n elements is:
- A.O(n)
- B.O(n log n)
- C.O(log n)
- D.O(n squared)
Show answer
Binary search compares the key with the middle element and throws away half the array at every step, so the number of comparisons grows with the logarithm of the array size; an array of a million sorted items needs about twenty comparisons.
Read the full explanation →