GATE CS 2021 Set 2 Q.18 (CS Q.8): Divide and Conquer

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

$O(\sqrt{n})$

$O(\log_2(n))$

$O(n^2)$

$O(n)$

Official answer and solution

Official answer: B
From: Official GATE 2021 answer key

Solution

Set up and solve the recurrence relation for the number of arithmetic operations performed by recursive binary search.

In recursive binary search on an array of size $n$ , each recursive step computes the midpoint index, typically via $\text{mid} = \text{low} + (\text{high} - \text{low}) / 2$ or $(\text{low} + \text{high}) / 2$ , which requires a constant number of arithmetic operations $c$ .

The search then recurses on one half of the array of size at most $\lfloor n / 2 \rfloor$ . The recurrence relation for the worst-case arithmetic operations $T(n)$ is:

T(n) = T(\lfloor n / 2 \rfloor) + c, \quad T(1) = O(1)

By the Master Theorem (Case 2 with $a=1, b=2, k=0$ ), the solution to this recurrence is:

T(n) = O(\log_2 n)

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 18 of 65, printed as CS Q.8
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source