The recurrence relation for binary search algorithm is : 

The correct answer is T(n) = T(n/2) O (1).

Key Points

• The binary search algorithm is a search algorithm that finds the position of a target value within a sorted array.
• Binary search works by repeatedly dividing the search interval in half.
• If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
• Otherwise, narrow it to the upper half. Repeat until the value is found or the interval is empty.

Additional Information

• The recurrence relation for the binary search algorithm is T(n) = T(n/2) + O(1).
• This is because at each step, the algorithm divides the problem size by 2 (hence T(n/2)) and performs a constant amount of work (O(1)).
• The time complexity of binary search is O(log n) in the worst case.
• Binary search is more efficient than linear search, especially for large datasets.