Q.Which of the following is correct recurrence relation for worst caset of binary search?
Correct answer: T(n) = T(n/2) + O(1)
T(1) = T(0) = O(1)
Explanation
In Binary Search, we first compare the given element with middle of the array. If given element matches with middle element, then we return middle index otherwise, we either recur for left half of array or right half of array. So recurrence is T (n) = T (n/2) + O (1) and T (1) = T (0) = O (1).
In Binary Search, we first compare the given element with middle of the array. If given element matches with middle element, then we return middle index otherwise, we either recur for left half of array or right half of array. So recurrence is T (n) = T (n/2) + O (1) and T (1) = T (0) = O (1).