15
Jul
This section analyzes the complexity of several well-known algorithms: binary search, selection sort, and Tower of Hanoi. Analyzing Binary Search The binary search algorithm presented in BinarySearch.java, searches for a key in a sorted array. Each iteration in the algorithm contains a fixed number of operations, denoted by c. Let T(n) denote the time complexity for a binary search on a list of n elements. Without loss of generality, assume n is a power of 2 and k = logn. Since a binary search eliminates half of the input after two comparisons, Ignoring constants and nondominating terms, the complexity of…