Algorithms Analysis Practice Test

The time complexity of performing a binary search on a sorted array of size n is O(log n). This efficiency arises from the way binary search operates: it repeatedly divides the search interval in half.

Initially, binary search starts by examining the middle element of the array. If the middle element is equal to the target value, the search is successful. If the target value is less than the middle element, the search focuses on the left half of the array; if greater, it narrows down to the right half. Each division of the search space reduces the number of elements to examine by half, leading to a logarithmic decrease in the number of comparisons required to find the target value.

This logarithmic property can be mathematically expressed as needing approximately log2(n) comparisons in the worst-case scenario. Therefore, for an array of size n, as n increases, the number of operations grows much slower than linear, confirming the O(log n) time complexity of binary search.