Algorithms
October 12, 2023GATE 2021 CSSet2
October 12, 2023Algorithms
Question 35

The recurrence relation that arises in relation with the complexity of binary search is:
T(n) = T(n/2) + k, k a constant


T(n) = 2T(n/2) + k, k a constant


T(n) = T(n/2) + log n


T(n) = T(n/2) + n

Question 35 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
∴ T(n) = 2T(n/2) + k, k a constant
Correct Answer: A
Question 35 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
∴ T(n) = 2T(n/2) + k, k a constant
Subscribe
Login
0 Comments