Skip to content
GATETECH
Official PYQ · 2021Set 2 · Q8Searching, Sorting, HashingMCQ1 mark

GATE CS 2021 Set 2 Q8 — Searching, Sorting, Hashing

Explain with AI

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

Choose one option
View worked solution

Answer: B

The recurrence relation for the number of arithmetic operations T(n)T(n) performed by a recursive binary search on a sorted array of size nn is given by:

T(n)=T(n2)+cT(n) = T\left(\frac{n}{2}\right) + c

where cc is a constant representing the number of basic arithmetic operations (such as addition, subtraction, and division) required to compute the middle index mid=low+⌊(high−low)/2⌋mid = low + \lfloor(high - low)/2\rfloor and update the search boundaries in each recursive step.

Solving this recurrence relation using iterative substitution:

T(n)=T(n2)+c=T(n4)+2c=⋯=T(1)+clog⁡2n=Θ(log⁡2n)T(n) = T\left(\frac{n}{2}\right) + c = T\left(\frac{n}{4}\right) + 2c = \dots = T(1) + c \log_2 n = \Theta(\log_2 n)

Thus, the worst-case number of arithmetic operations is Θ(log⁡2n)\Theta(\log_2 n).

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Searching, Sorting, Hashing questions