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 the binary search algorithm is O(logn). An algorithm with the O(logn) time complexity is called a logarithmic algorithm and it exhibits a logarithmic growth rate. The base of the log is 2, but the base does not affect a logarithmic growth rate, so it can be omitted. The logarithmic algorithm grows slowly as the problem size increases. In the case of binary search, each time you double the array size, at most one more comparison will be required. If you square the input size of any logarithmic time algorithm, you only double the time of execution. So a logarithmic-time algorithm is very efficient.
Analyzing Selection Sort
The selection sort algorithm presented in SelectionSort.java, finds the smallest element in the list and swaps it with the first element. It then finds the smallest element remaining and swaps it with the first element in the remaning list, and so on until the remaining list contains only one element left to be sorted. The number of comparisons is n - 1 for the first iteration, n - 2 for the second iteration, and so on. Let T(n) denote the complexity for selection sort and c denote the total number of other operations such as assignments and additional comparisons in each iteration. Thus,
Therefore, the complexity of the selection sort algorithm is O(n^2).
Analyzing the Tower of Hanoi Problem
The Tower of Hanoi problem presented in TowerOfHanoi.java, recursively
moves n disks from tower A to tower B with the assistance of tower C as follows:
- Move the first n - 1 disks from A to C with the assistance of tower B.
- Move disk n from A to B.
- Move n - 1 disks from C to B with the assistance of tower A.
The complexity of this algorithm is measured by the number of moves. Let T(n) denote the number of moves for the algorithm to move n disks from tower A to tower B with T(1) = 1. Thus,
An algorithm with O(2n) time complexity is called an exponential algorithm, and it exhibits an exponential growth rate. As the input size increases, the time for the exponential algorithm grows exponentially. Exponential algorithms are not practical for large input size. Suppose
the disk is moved at a rate of 1 per second. It would take 2^32/(365*24*60*60) = 136 years to move 32 disks and 2^64/(365*24*60*60) = 585 billion years to move 64 disks.
Common Recurrence Relations
Recurrence relations are a useful tool for analyzing algorithm complexity. As shown in the preceding examples, the complexity for binary search, selection sort, and the Tower of Hanoi is
respectively. Table below summarizes the common recurrence relations.
Comparing Common Growth Functions
The preceding sections analyzed the complexity of several algorithms. Table below lists some common growth functions and shows how growth rates change as the input size doubles from n = 25 to n = 50.
These functions are ordered as follows, as illustrated in Figure below.
