...
GATE 1994
October 12, 2023
GATE 2021 CS-Set-2
October 12, 2023
GATE 1994
October 12, 2023
GATE 2021 CS-Set-2
October 12, 2023

Algorithms

Question 19

The recurrence relation that arises in relation with the complexity of binary search is:

A
T(n) = T(n/2) + k, k a constant
B
T(n) = 2T(n/2) + k, k a constant
C
T(n) = T(n/2) + log n
D
T(n) = T(n/2) + n
Question 19 Explanation: 
In binary search, search for the half of the list and constant time for comparing. So,
∴ T(n) = 2T(n/2) + k, k a constant
Correct Answer: A
Question 19 Explanation: 
In binary search, search for the half of the list and constant time for comparing. So,
∴ T(n) = 2T(n/2) + k, k a constant

Leave a Reply

Your email address will not be published. Required fields are marked *