Big-O Notation for Discrete Math

The formal definition of big-O

We say f(n) = O(g(n)) if there exist constants c greater than 0 and n0 such that 0 is at most f(n) and f(n) is at most c times g(n) for all n at least n0. Read that carefully, because both quantifiers matter. The constant c lets you ignore multiplicative factors, so 5n and n differ by nothing that big-O can see. The threshold n0 lets you ignore small inputs entirely, so a function may misbehave near zero and still satisfy the bound.

The definition is a promise about the tail of the function, nothing more. Proving a big-O claim means producing a specific c and n0 and showing the inequality holds beyond that point. Take f(n) = 3n^2 + 5n + 7. For every n at least 1 we have n at most n^2 and 1 at most n^2, so f(n) is at most 3n^2 + 5n^2 + 7n^2, which is 15n^2. So c = 15 and n0 = 1 witness f(n) = O(n^2). Any other valid pair would do; the definition asks only that some pair exists.

• f(n) = O(g(n)) iff there are c greater than 0 and n0 with 0 at most f(n) at most c g(n) for all n at least n0.
• The constant c absorbs multiplicative factors, so coefficients never appear.
• The threshold n0 makes small-input behaviour irrelevant.
• To prove a claim, exhibit one working pair of c and n0.

Big-O is an upper bound, not a tight one

This is the point most often misused. Big-O gives a ceiling and says nothing about whether that ceiling is close. Since 3n^2 + 5n + 7 is at most 15n^2 for n at least 1, and n^2 is at most n^3 for n at least 1, the same function is also O(n^3), and O(n^100), and O(2^n). All of these are true statements. They are merely weak ones, in the same way that saying a person is under three metres tall is true but uninformative.

So when someone says an algorithm is O(n^2), they have told you it is no worse than quadratic; strictly, they have not told you it is quadratic. In practice people often mean the tight bound and say big-O out of habit. If you want to claim a bound is tight, big-Theta is the notation that actually says so.

Omega and Theta

Big-Omega is the mirror image. We say f(n) = Omega(g(n)) if there exist c greater than 0 and n0 such that f(n) is at least c times g(n) for all n at least n0. It is a lower bound: the function grows at least this fast eventually. For the same f(n) = 3n^2 + 5n + 7, every term is positive, so f(n) is at least 3n^2 for all n at least 1, giving f(n) = Omega(n^2) with c = 3 and n0 = 1.

Big-Theta combines the two. We say f(n) = Theta(g(n)) when f(n) = O(g(n)) and f(n) = Omega(g(n)) both hold, meaning the function is squeezed between two constant multiples of g beyond some threshold. Our example is Theta(n^2), since 3n^2 is at most f(n) which is at most 15n^2 for all n at least 1. Theta is the honest way to say two functions grow at the same rate, and it is what you should reach for when describing an algorithm whose cost you actually know.

• O is an upper bound: grows no faster than.
• Omega is a lower bound: grows at least as fast as.
• Theta is both at once: grows at the same rate as.
• Theta(g) holds exactly when both O(g) and Omega(g) hold.

The common growth classes in order

Most functions you meet in discrete mathematics fall into a short list of classes, and knowing their order by heart is most of the practical skill. From slowest-growing to fastest: constant 1, then logarithmic log n, then linear n, then linearithmic n log n, then quadratic n^2, then cubic n^3, then exponential 2^n, then factorial n factorial. Each class is eventually overtaken by every class to its right, no matter what constant factors are attached.

The gaps between these classes are enormous, which is why constant factors lose. At n = 1024, log base 2 of n is 10, n log n is 10240, and n^2 is 1048576: the quadratic term is already a hundred times the linearithmic one and grows further apart from there. Note also that the base of a logarithm never matters inside asymptotic notation, because changing base multiplies by a fixed constant, and constants are exactly what the notation discards. So O(log n) needs no base.

• Ordering: 1, log n, n, n log n, n^2, n^3, 2^n, n factorial.
• Logarithm bases are irrelevant, since a base change is a constant factor.
• n factorial beats 2^n from n = 4 onward.
• Polynomials are classified by their highest-degree term alone.

How to compare two functions

For polynomials the rule is simple: drop every term except the one of highest degree, drop its coefficient, and you have the Theta class. This works because for large n the leading term dominates the sum, which is exactly the argument used above to bound 3n^2 + 5n + 7 above by 15n^2 and below by 3n^2. Sums in general behave the same way, since the class of a sum is the class of its fastest-growing part.

For anything less obvious, take the ratio f(n) divided by g(n) and ask what it does as n grows. If the ratio tends to 0 then f grows strictly slower, so f is O(g) but not Theta(g). If it tends to a positive constant, the two are in the same class and f is Theta(g). If it grows without bound, f grows strictly faster and is Omega(g) but not O(g). Products are easier still, since the class of a product is the product of the classes, which is how the n log n of a divide-and-conquer sort factorises into linear work at each of log n levels.

• Sums: keep the fastest-growing term, discard the rest.
• Products: multiply the classes of the factors.
• Ratio tends to 0: f grows strictly slower than g.
• Ratio tends to a positive constant: f and g are in the same Theta class.

Reading asymptotic claims carefully

Asymptotic notation describes growth, not cost at any specific input. An algorithm that is Theta(n log n) with a huge constant can be slower than a Theta(n^2) one across every size you will ever run, which is not a contradiction, only a reminder that n0 may sit far past the practical range. Insertion sort beating merge sort on tiny arrays is the familiar case, and it is why sorting libraries switch strategies below a threshold.

The other habit worth keeping is to say what you are measuring. A running time can be described in the worst case, the average case, or the best case, and each is a different function of n before any asymptotic class is attached. Quicksort is Theta(n log n) on average and Theta(n^2) in the worst case, and both facts are true of the same algorithm, so naming the case is part of the claim.