Mastering Algorithms With C - Kyle Loudon [24]
T(n) = c 1 + c 2 + n(c 3 + c 4 + c 5) + c 6
Using the rules of O -notation, this algorithm's complexity is O (n) because the constants are not significant. Analyzing an algorithm in terms of these constant costs is very thorough. However, recalling what we have seen about growth rates, remember that we do not need to be so precise. When inspecting the overall structure of an algorithm, only two steps need to be performed: we must determine which parts of the algorithm depend on data whose size is not constant, and then derive functions that describe the performance of each part. All other parts of the algorithm execute with a constant cost and can be ignored in figuring its overall complexity.
Assuming T (n) in the previous example represents an algorithm's running time, it is important to realize that O (n), its complexity, says little about the actual time the algorithm will take to run. In other words, just because an algorithm has a low growth rate does not necessarily mean it will execute in a small amount of time. In fact, complexities have no real units of measurement at all. They describe only how the resource being measured will be affected by a change in data size. For example, saying that T (n) is O (n) conveys only that the algorithm's running time varies proportionally to n, and that n is an upper bound for T (n) within a constant factor. Formally, we say that T (n) ≤ cn, where c is a constant factor that accounts for various costs not associated with the data, such as the type of computer on which the algorithm is running, the compiler used to generate the machine code, and constants in the algorithm itself.
Many complexities occur frequently in computing, so it is worthwhile to become familiar with them. Table 4.1 lists some typical situations in which common complexities occur. Table 4.2 lists these common complexities along with some calculations illustrating their growth rates. Figure 4.1 presents the data of Table 4.2 in a graphical form.
Table 4.1. Some Situations Wherein Common Complexities Occur
Complexity
Example
O(1)
Fetching the first element from a set of data
O(lg n)
Splitting a set of data in half, then splitting the halves in half, etc.
O(n)
Traversing a set of data
O(n lg n)
Splitting a set of data in half repeatedly and traversing each half
O(n 2)
Traversing a set of data once for each member of another set of equal size
O(2n )
Generating all possible subsets of a set of data
O(n!)
Generating all possible permutations of a set of data
Table 4.2. The Growth Rates of the Complexities in Table 4.1
n = 1
n = 16
n = 256
n = 4K
n = 64K
n = 1M
O(1)
1.000E+00
1.000E+00
1.000E+00
1.000E+00
1.000E+00
1.000E+00
O (lg n)
0.000E+00
4.000E+00
8.000E+00
1.200E+01
1.600E+01
2.000E+01
O (n)
1.000E+00
1.600E+01
2.560E+02
4.096E+03
6.554E+04
1.049E+06
O (n lg n)
0.000E+00
6.400E+01
2.048E+03
4.915E+04
1.049E+06
2.097E+07
O (n 2)
1.000E+00
2.560E+02
6.554E+04
1.678E+07
4.295E+09
1.100E+12
O (2n )
2.000E+00
6.554E+04
1.158E+77
—
—
—
O (n!)
1.000E+00
2.092E+13
—
—
—
—
Figure 4.1. A graphical depiction of the growth rates in Tables Table 4.1 and Table 4.2
Just as the complexity of an algorithm says little about its actual running time, it is important to understand that no measure of complexity is necessarily efficient or inefficient. Although complexity is an indication of the efficiency of an algorithm, whether a particular complexity is considered efficient or inefficient depends on the problem. Generally, an efficient algorithm is one in which we know we are doing the best we can do given certain criteria. Typically, an algorithm is said to be efficient if there are no algorithms with lower complexities to solve the same problem and the algorithm does not contain excessive constants. Some problems are intractable, so there are no "efficient" solutions without settling