Algorithms

Question 15

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

Question 15 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 15 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