Which of the following is correct recurrence relation for worst case of binary…
2018
Which of the following is correct recurrence relation for worst case of binary search?
Answer: C. T(n) = T(n/2) + O(1) T(1) = T(0) = O(1) — Binary search divides the input array into two halves at each step, making one recursive call on n/2 elements. The comparison operation takes constant time…
- 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 229 students.
Show answer & explanation
Correct answer: C
Binary search divides the input array into two halves at each step, making one recursive call on n/2 elements. The comparison operation takes constant time O(1). Thus, the worst-case recurrence relation is T(n) = T(n/2) + O(1).
Loading lesson…