sum and product rules for Big-O

Once you can bound individual pieces of a program, you need rules for gluing those bounds together: what is the cost of doing one thing then another (a sum), or of nesting one inside another (a product)? Two simple rules cover almost every analysis you will do, and they are exactly how you turn a line-by-line reading of code into a single Big-O.

The sum rule: if you run a block costing O(f) and then a block costing O(g), the total is O(f + g), which simplifies to O of the larger of f and g. This is because for large n the bigger function dominates: O(n) followed by O(n^2) is O(n^2), since the linear part is swallowed. This is the formal reason we keep only the dominant term in a sum like n^2 + n + 1. The product rule: if you do something costing O(g) once for each of O(f) repetitions — a loop running f times with g work inside each pass — the total is O(f times g). A loop of n iterations each doing O(n) work is O(n times n) = O(n^2). These rules also let you handle a constant times a function: O(c times f) = O(f), because constant factors vanish.

Together these turn analysis into bookkeeping. Sequential code: add the costs and keep the max. Nested code: multiply the costs. Constant-factor scaling: ignore it. A subtle honesty note: the sum rule keeps the maximum only when the number of summed blocks is a CONSTANT. If you sum a growing number of terms — say the i-th iteration costs i and you sum over i from 1 to n — you cannot just take the max term n; you must actually total them, giving n(n+1)/2 = Theta(n^2), not Theta(n). Counting loop iterations carefully is where that distinction lives.