big-O notation
/ big oh /
Suppose you want to say how big something is without pinning down its exact value — like saying a crowd is 'in the thousands' rather than counting every head. Big-O notation is that kind of honest upper bound for functions. When we write f(x) = O(g(x)), we are claiming that f never grows faster than g, up to a fixed constant factor, in whatever limit we care about (x going to infinity, or x going to zero).
The precise meaning: f(x) = O(g(x)) as x tends to a limit means there is a constant C and a neighbourhood of that limit in which the absolute value of f(x) stays below C times the absolute value of g(x). So O(g) is the set of all functions eventually dominated by a constant multiple of g. For example, 3x^2 + 5x = O(x^2) as x goes to infinity, because for large x the x^2 term sets the scale and the constant C = 4 works comfortably. Near x = 0 the same notation is read the other way: sin x - x = O(x^3) means the leftover, after subtracting x, is no larger than a constant times x^3 when x is small.
This is the basic grammar of all asymptotics, and it shows up everywhere: in the error term of a Taylor expansion (f(x) = f(0) + f'(0) x + O(x^2)), in the cost of an algorithm (sorting in O(n log n)), and in the remainder of an asymptotic series. The honest caveat is that big-O hides the constant entirely. O(x^2) tells you the shape of the growth but says nothing about whether the constant is 0.001 or 10^9, so two O(n^2) methods can differ wildly in practice.
e^x = 1 + x + x^2/2 + O(x^3) as x tends to 0; and x^2 + 100x = O(x^2) as x tends to infinity.
The same symbol O describes a small leftover near 0 and a growth rate near infinity — the limit must always be stated.
f = O(g) is a one-way claim, not an equation: you may not 'cancel' the O, and you cannot reverse it to g = O(f). It bounds f from above by g, nothing more.