Multiple choice

The recurrence relation that arises in relation with the complexity of Binary Search is

  1. T(n) = T(n/2) + k

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

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

  4. T(n) = T(n/2) + n
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Binary Search works by dividing the search space in half during each step and performing a constant amount of work to compare the middle element. This gives the recurrence relation T(n) = T(n/2) + k, where n is the size of the array and k is the constant time for comparison.

Keep practicing — related questions