Big O Example: Simplifying 3n² + 5n + 2

Turning a cost into its Big O class takes two rules, applied in order: keep the term that grows fastest, then drop its constant factor, the number it is multiplied by. This example applies both to 3n² + 5n + 2 and shows, in numbers, why each rule is safe.

A function that compares items in pairs might do 3n² + 5n + 2 steps on n items. Its three terms grow at different rates. The table shows how much of the total each makes up as n grows.

At n = 10, the two smaller terms are still about 15 per cent of the total. At n = 10,000, 5n is 0.02 per cent and the 2 is under 0.01 per cent. These are lower-order terms: their share keeps shrinking towards nothing, so rule one keeps 3n² alone.

Rule two drops the 3. When n doubles, the total grows 3.70 times from n = 10, 3.97 times from n = 100 and 4.00 times from n = 10,000. That factor of four is what n² does on its own, so the 3 changes how large the cost is, never how it grows. The class is O(n²). Writing O(3n²) is not false, since it is the same growth, but a class is always written in its simplest form.

The two rules apply to any cost written as a sum of terms. Any an² + bn + c with a positive a is O(n²), whatever b and c are. And 7n + 1,000 is O(n), even though the constant is the larger term while n is small, because Big O describes what happens as n grows large.