Which of the following is the correct recurrence relation for the worst case…
2018
Which of the following is the correct recurrence relation for the worst case of binary search?
- A.
T(n) = 2T(n/2) + O(1) ;
T(1) = T(0) = O(1)
- B.
T(n) = T(n/2) + O(n) ;
T(1) = T(0) = O(1)
- C.
T(n) = T(n/2) + O(1) ;
T(1) = T(0) = O(1)
- D.
T(n) = T(n/2) + O(log n) ;
T(1) = T(0) = O(1)
Attempted by 311 students.
Show answer & explanation
Correct answer: C
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 relation for the worst case is: T(n)=T(n/2)+O(1)