Simplifying Rules

Once you determine the running-time equation for an algorithm, it really is a simple matter to derive the big-Oh expressions from the equation. You do not need to resort to the formal definitions of asymptotic analysis. Instead, you can use the following rules to determine the simplest form.

1. If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n).
2. If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n))
3. If f₁(n) is in O(g₁(n)) and f₂(n) is in O(g₂(n)), then f₁(n)+f₂(n) is in O(max(g₁(n), g₂(n)))
4. If f₁(n) is in O(g₁(n)) and f₂(n) is in O(g₂(n)), then f₁(n)f₂(n) is in O(g₁(n)g₂(n))

The first rule says that if some function g(n) is an upper bound for your cost function, then any upper bound for g(n) is also an upper bound for your cost function.

The significance of rule (2) is that you can ignore any multiplicative constants in your equations when using big-Oh notation.

Rule (3) says that given two parts of a program run in sequence (whether two statements or two sections of code), you need consider only the more expensive part.

Rule (4) is used to analyze simple loops in programs. If some action is repeated some number of times, and each repetition has the same cost, then the total cost is the cost of the action multiplied by the number of times that the action takes place.

Taking the first three rules collectively, you can ignore all constants and all lower-order terms to determine the asymptotic growth rate for any cost function. The advantages and dangers of ignoring constants were discussed near the beginning of this section. Ignoring lower-order terms is reasonable when performing an asymptotic analysis. The higher-order terms soon swamp the lower-order terms in their contribution to the total cost as (n) becomes larger. Thus, if T(n)=3n⁴+5n², then T(n) is in O(n⁴). The n² term contributes relatively little to the total cost for large n.

From now on, we will use these simplifying rules when discussing the cost for a program or algorithm.