A Level Computer Science OCR Practice Exam

What is the space complexity of Binary Search?

1. O(n)

2. O(1)

3. O(log n)

4. O(n log n)

The correct answer is: O(1)

The space complexity of binary search is O(1) when it is implemented iteratively. This means that the algorithm uses a constant amount of space regardless of the size of the input data. In binary search, an array or a sorted list is being searched, which requires only a few pointers or variables to keep track of the left and right indices as well as the midpoint. The actual size of the array does not affect the amount of additional memory needed for these operations. Thus, the space required remains constant. When binary search is implemented recursively, the space complexity could be O(log n) due to the stack space created by recursive calls. However, the question likely pertains to the iterative version, which is why O(1) is the correct answer in this context. The other options describe complexities for different scenarios or algorithms that do not apply here.