What is the Big-O time complexity of binary search on a sorted array of length n?

Prepare for the 241 Computer Science Certification Exam with comprehensive flashcards and multiple choice questions. Enhance knowledge with explanations and hints to excel in your test journey!

Multiple Choice

What is the Big-O time complexity of binary search on a sorted array of length n?

Binary search takes advantage of the sorted order to cut the search space in half with every comparison. You look at the middle element and compare it to your target; if it matches, you’re done, and if not, you discard the half that cannot contain the target. Each step halves the number of candidate elements, so after k comparisons you’re left with about n/2^k possibilities. To isolate a single item you need 2^k ≈ n, which means k ≈ log2(n). In Big-O terms, the worst-case time grows logarithmically with n, so the time complexity is O(log n). This is faster than scanning the whole array (O(n)) and certainly not constant time (O(1)).

Binary search takes advantage of the sorted order to cut the search space in half with every comparison. You look at the middle element and compare it to your target; if it matches, you’re done, and if not, you discard the half that cannot contain the target. Each step halves the number of candidate elements, so after k comparisons you’re left with about n/2^k possibilities. To isolate a single item you need 2^k ≈ n, which means k ≈ log2(n). In Big-O terms, the worst-case time grows logarithmically with n, so the time complexity is O(log n). This is faster than scanning the whole array (O(n)) and certainly not constant time (O(1)).

More practice questions