GATE 1994
October 12, 2023GATE 2021 CS-Set-2
October 12, 2023Algorithms
| Question 19 |
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 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
∴ 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
∴ T(n) = 2T(n/2) + k, k a constant