Algorithms
October 12, 2023GATE 2021 CS-Set-2
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