What is the worst-case number of arithmetic operations performed by recursive binary search on a sor

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2021 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2021 question covers Searching topic.

Q: What is the difficulty level of this question?

This GATE-CS 2021 Algorithm question has a easy difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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

Accepted Answer

Correct Answer: (C) Theta(log_2 n)Concept -- Binary Search Time Complexity (from Cormen et al., Introduction to Algorithms, Chapter 2):Binary search works by repeatedly halving the search space. At each recursive step, one arithmetic operation (computing the midpoint: mid = (low + high) / 2) and one comparison are performed. The array size reduces from n to n/2 at each step. The number of recursive calls is at most floor(log_2 n) + 1 (in the worst case, when the element is not found or found at the last comparison).Recurrence: T(n) = T(n/2) + O(1). By the Master Theorem (case 2 of T(n) = aT(n/b) + f(n) with a=1, b=2, f(n)=O(1)), T(n) = Theta(log n). Specifically Theta(log_2 n) arithmetic operations in the worst case.

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

Master GATE-CS with Our Test Series

Frequently Asked Questions

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

Master GATE-CS with Our Test Series

Frequently Asked Questions