Every later claim in this course, such as "a heap insertion takes logarithmic time" or "union-find is nearly constant", is a statement about how a cost grows with the input size. Such a statement is only meaningful once we say what is counted, what the input size is, which inputs are considered, and what the symbols , and mean exactly. This unit supplies those foundations. It uses no data structure; later units on dynamic arrays, heaps and sorting rely on it.
Cost models
A stopwatch measures one machine, one compiler and one input. To reason about algorithms themselves we count abstract operations.
Definition 19.1.1
(Unit-cost RAM model, input size, cost function)
In the unit-cost RAM model each of the following costs one step: an arithmetic operation or comparison on a word of fixed width, reading or writing one array cell or variable, and a jump. The input size is a stated parameter: the number of array elements, the number of vertices and edges, or the number of bits of a number. For an algorithm and an input let be the number of steps. The worst-case cost is
the best-case cost takes the minimum, and the average-case cost takes the expectation under a stated probability distribution on inputs of size .
Several variants matter. In a comparison model only key comparisons are counted, as in the sorting lower bound. In a bit-cost model arithmetic on a number with bits costs about steps, which matters when numbers are not bounded by the word size. The unit-cost assumption can mislead if numbers grow: repeated squaring of an integer doubles its length each time, so counting each squaring as one step understates the work. A cost claim is therefore always relative to a model, and the input size must be measured in that model. For an integer given in binary, the input size is bits, so an algorithm that loops times is exponential in the input size.
The notation
Definition 19.1.2
(, and )
Let . Write if there exist constants and such that for all . Write if there exist and with for all . Write if both hold, that is, and .
The constants may depend on and but not on . The notation describes behavior for large only: the threshold discards finitely many small inputs. The equals sign is a convention; stands for the set of functions bounded above by a constant multiple of , and "" means belongs to it. The symbol gives an upper bound only: a linear algorithm is also , which is true but uninformative. is the statement that the order of growth is exactly that of .
Proposition 19.1.3
(Calculus of growth rates)
Let .
- Constants and lower terms. If with real coefficients and , then there are and with for all ; that is, .
- Sums. If and then .
- Products. If and then .
- Transitivity. If and then .
Proof
(Absorbing lower terms, and multiplying constants)
(1) A constant is with , so let and . For every with is at most , hence . Upper bound: for . Lower bound: . If then , so . Take , and .
(2) Choose and for the two hypotheses. For , .
(3) For the same , all quantities are nonnegative, so the two inequalities may be multiplied: .
(4) If for and for , then for .
Proof X-ray
Where the polynomial threshold comes from
Only the lower bound in (1) uses ; the upper bound would work with . The key move is to gather all lower terms into the single quantity , so that the comparison with the leading term becomes one inequality in : . The threshold is the point from which the leading term dominates by a factor of at least two, and it depends on the coefficients, not only on . For we get , , , and indeed exactly when (at , ). No threshold such as can work here, since . If the lower bound fails for every , because is eventually negative.
For the logarithm, , so all bases differ by a constant factor and the base is omitted inside and .
A growth hierarchy
For large the standard orders increase in this sequence:
where means but . Two comparisons illustrate the proofs. First, : since for , we have . Second, is not for any fixed . Put . Then , which tends to , so for all large each step multiplies by at most , and . Hence is unbounded. We shall use the rest of the hierarchy as a standard fact.
Proposition 19.1.4
(Limit criterion for )
If with , then .
Proof
(Squeezing the ratio)
Take in the definition of the limit. Eventually lies between and , so for all large , which gives both bounds required by .
Concept lensAnalytic
The notation as limit superior and inferior
When for large , the constants can be replaced by two limiting quantities: exactly when , and exactly when . For and the ratio alternates between and , so and : although the ordinary limit does not exist.
Counting steps in code
Count the number of executions of the innermost statement, then simplify. For nested loops multiply when the inner trip count does not depend on the outer index; otherwise sum. A loop whose control variable doubles runs about times.
Worked examples
Worked example 19.1.5
(A quadratic polynomial with explicit constants)
Show that . Lower bound: for all , so , works. Upper bound: for we have and , hence , so , works. Therefore . Check at : , and .
Worked example 19.1.6
(Counting loop iterations)
Consider for i in range(n): for j in range(i): work(). The body runs times for , once for , and times in general, in total . For this is 10. Since and, for , , the count is .
Now consider i = 1; while i < n: i = 2*i. The values of are , and the loop stops once . For the tested values are below 10, giving 4 iterations . For the values give 3 iterations . In general iterations run for , which is for .
Worked example 19.1.7
( without a limit)
Let . For even we get and for odd we get ; for example and . Hence for all , so with , , . The ratio alternates between and and has no limit, so the limit criterion does not apply, yet the definition still does. The limit criterion is sufficient, not necessary.
Subtle points
Counterexample mode
Constant in the exponent
Is ? No. , and is unbounded, so no constant satisfies for all large . By contrast . A constant in the exponent changes the growth class; a constant factor does not.
Common mistake
(Reading the equals sign symmetrically)
From one may not write , and from and one may not conclude . The sign means membership: belongs to the set . Indeed is false, since is unbounded.
Common mistake
(Mixing up worst case and O)
"Worst case" and "" are independent ideas: bounds a function, while worst case selects which function. One may state a best-case cost with and a worst-case cost with .
Comparing algorithms by growth rate ignores constants: exceeds whenever , so a quadratic algorithm can be faster on small inputs. Asymptotics predicts scaling, such as how time changes when doubles, not the running time at a particular .
Exercises with solutions
Quick check
(1. Prove that is .)
Solution · Solution 1
For we have , so . Then for all . Hence , , show .
Quick check
(2. Compute how many times the inner statement runs: for : set ; while : set . Evaluate it for and give the growth class.)
Solution · Solution 2
For a given the values of are with , so the body runs times. For the counts for are , with sum . In general the total is at most . At least of the indices satisfy , and each of these contributes at least , so the total is at least . Both bounds are of order , so the total is .
Quick check
(3. True or false, with a reason: (a) ; (b) ; (c) ; (d) ; (e) .)
Solution · Solution 3
(a) True: . (b) False: the ratio is , which is unbounded. (c) True: for . (d) False: is unbounded. (e) True: , a constant multiple of .
Quick check
(4. An algorithm with takes 8 ms on . Predict the time for . What would it be if were assumed instead, approximately?)
Solution · Solution 4
For , tripling multiplies the time by , giving ms. For , the ratio is . Since and , the ratio is about , so about ms. The prediction depends on the assumed growth class, which is why the model must be justified.
Quick check
(5. Order by growth: , , , , , . Then find the smallest such that for all .)
Solution · Solution 5
Increasing order: . For the threshold: , , , , so fails at and holds at . It continues to hold: if with , then because for . So .