Q13: Time complexity of binary search algorithm

Posted on by bytesoftheday

Question #13: Which of the following recursive equation holds true for the binary search algorithm?

Options:

  1. T(n) = T(n-1) + 1
  2. T(n) = T(n/2) + 1
  3. T(n) = 2T(n/2) +1
  4. T(n) = T(log(n)) +1

 

Solution:

After every step, the problem gets reduced to half the original size since the number we search lies in either first half or second half. See the following example:

binary-search-program-shell

This gets evaluated to:

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

=> T(n) = T(n/4) + 1 + 1

=> T(n) = T(n/8) + 1 + 1 + 1

=>T(n) = log(n) + constant

Hence, the correct answer is option 2.