Question

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size \(n\)?

• A. \(\Theta(\sqrt{n})\)
• B. \(\Theta(\log_2 n)\)
• C. \(\Theta(n^2)\)
• D. \(\Theta(n)\)

Hint:

Binary search reduces the problem size by half at each step, leading to logarithmic time complexity.

Answer 1

The Correct Option is B

Step 1: Understand the working of recursive binary search.
Binary search works by repeatedly dividing the search interval into two halves. At each recursive step, the size of the array is reduced from \(n\) to \(n/2\).

Step 2: Count the number of recursive calls.
The recursion continues until the search space reduces to size 1. The number of times \(n\) can be divided by 2 until it becomes 1 is: \[ \log_2 n \] Each recursive call performs a constant number of arithmetic operations.

Step 3: Determine worst-case complexity.
In the worst case, the element is either found at the last step or not found at all. Hence, the total number of arithmetic operations is proportional to the number of recursive calls.

Step 4: Conclusion.
Therefore, the worst-case number of arithmetic operations is: \[ \Theta(\log_2 n) \]

Final Answer: (B)