Mastering Algorithms With C - Kyle Loudon [23]
O(c) = O(1)
Multiplicative constants are omitted. When analyzing the running time of an algorithm, apply this rule when you have a number of tasks that all execute in the same amount of time. For example, if three tasks each run in time T (n) = n, the result is O (3n), which simplifies to O (n). Formally stated, for some constant c:
O(cT) = cO(T) = O(T)
Addition is performed by taking the maximum. When analyzing the running time of an algorithm, apply this rule when one task is executed after another. For example, if T 1(n) = n and T 2(n) = n 2 describe two tasks executed sequentially, the result is O (n) + O (n 2), which simplifies to O (n 2). Formally stated:
O(T 1)+O(T 1+T 2) = max (O(T 1), O(T 2))
Multiplication is not changed but often is rewritten more compactly. When analyzing the running time of an algorithm, apply this rule when one task causes another to be executed some number of times for each iteration of itself. For example, in a nested loop whose outer iterations are described by T 1 and whose inner iterations by T 2, if T 1(n) = n and T 2(n) = n, the result is O (n)O (n), or O (n 2). Formally stated:
O(T 1)O(T 2) = O(T 1 T 2)
O-Notation Example and Why It Works
The next section discusses how these rules help us in predicting an algorithm's performance. For now, let's look at a specific example demonstrating why they work so well in describing a function's growth rate. Suppose we have an algorithm whose running time is described by the function T (n) = 3n 2 + 10n + 10. Using the rules of O -notation, this function can be simplified to:
O(T(n)) = O(3n 2 + 10n + 10) = O(3n 2) = O(n 2)
This indicates that the term containing n 2 will be the one that accounts for most of the running time as n grows arbitrarily large. We can verify this quantitatively by computing the percentage of the overall running time that each term accounts for as n increases. For example, when n = 10, we have the following:
Running time for 3n 2: 3(10)2/(3(10)2 + 10(10) + 10) = 73.2%
Running time for 10n: 10(10)/(3(10)2 + 10(10) + 10) = 24.4%
Running time for 10: 10/(3(10)2 + 10(10) + 10) = 2.4%
Already we see that the n 2 term accounts for the majority of the overall running time. Now consider when n = 100:
Running time for 3n 2: 3(100)2/(3(100)2 + 10(100) + 10) = 96.7% (Higher)
Running time for 10n: 10(100)/(3(100)2 + 10(100) + 10) = 3.2% (Lower)
Running time for 10: 10/(3(100)2 + 10(100) + 10) < 0.1% (Lower)
Here we see that this term accounts for almost all of the running time, while the significance of the other terms diminishes further. Imagine how much of the running time this term would account for if n were 106!
Computational Complexity
When speaking of the performance of an algorithm, usually the aspect of interest is its complexity, which is the growth rate of the resources (usually time) it requires with respect to the size of the data it processes. O -notation describes an algorithm's complexity. Using O -notation, we can frequently describe the worst-case complexity of an algorithm simply by inspecting its overall structure. Other times, it is helpful to employ techniques involving recurrences and summation formulas (see the related topics at the end of the chapter), and statistics.
To understand complexity, let's look at one way to surmise the resources an algorithm will require. It should seem reasonable that if we look at an algorithm as a series of k statements, each with some cost (usually time) to execute, ci , we can determine the algorithm's total cost by summing the costs of all statements from c 1 to ck in whatever order each is executed. Normally statements are executed in a more complicated manner than simply in sequence, so this has to be taken into account when totaling the costs. For example, if some subset of the statements is executed in a loop, the costs of the subset must be multiplied by the number of iterations. Consider an algorithm consisting of k = 6 statements. If statements 3, 4,