How much time is required by the binary search algorithm in the worst case? Each pass through the loop requires at most a constant amount of work. The time to execute the algorithm will then be determined by the number of passes through the loop, plus, of course, a constant time for initialization and finalization. What is the greatest number of loop iterations executed?
In each pass through the loop, the search involves at most half the elements that were under consideration during the preceding pass through the loop. Starting with n elements, after one pass through the loop at most 1/2n elements are left, after two passes through the loop at most 1/2(1/2)n elements, after three passes at most 1/2(1/2)2n elements, and after k passes at most 1/2(1/2)k-1n or 1/2kn elements. This number, 1/2kn, is less than 1 when -k + 1g n < 0 or when k > 1g n. This means that the loop cannot be executed more than ?/FONT>lg n?/FONT> times. If n is 20, for example, then 1g 20 = 4.32, and ?/FONT>4.32?/FONT> is 5. Thus in the worst case, the binary search is O(1gn). If each record stored is searched with equal frequency, then the average time to find a stored record is actually about (1g n) - 1.(The proof is not given here.)