Which of the following is the correct recurrence relation for the worst case…

2018

Answer: C. T(n) = T(n/2) + O(1) ; T(1) = T(0) = O(1) — In binary search , at each step the problem size is reduced to half (n/2) and only constant work O(1) is done for comparison. Therefore, the recurrence…

1. A.

   T(n) = 2T(n/2) + O(1) ;

   T(1) = T(0) = O(1)

2. B.

   T(n) = T(n/2) + O(n) ;

   T(1) = T(0) = O(1)

3. C.

   T(n) = T(n/2) + O(1) ;

   T(1) = T(0) = O(1)

4. D.

   T(n) = T(n/2) + O(log n) ;

   T(1) = T(0) = O(1)

Attempted by 453 students.