Explain why the complexity of binary search is expressed through the logarithm of the execution time.

Binary search works on a sorted array, dividing the search area in half each time. At each step, it eliminates half of the remaining elements, so the number of elements to check decreases geometrically.

If initially there are n elements, after the first step there are n/2, then n/4, n/8, and so on, until only 1 element remains. The number of such divisions is the number of steps of the algorithm, which is equal to the number k for which ( n / 2^k = 1 ).

Solving the equation, we get:

[ 2^k = n \implies k = \log_2 n ]

Thus, the runtime of binary search is proportional to the logarithm of the input size, i.e., (O(\log n)). This is much more efficient than linear search with (O(n)).