Asymptotic Notation Made Precise

Big-O notation is a promise about the long run. When we say a running time is O(g(n)), we mean there is some constant multiple of g, like 3 times g or 100 times g, that the running time never passes once the input is big enough. So O is an upper bound that holds from some starting size onward, not a exact prediction for every input.

Its close cousin, big-Theta, is a two-sided promise. Saying a running time is Theta(g(n)) means it is sandwiched between two constant multiples of g, one above and one below, for large enough inputs. That tells you the growth rate exactly, up to a constant factor.

Binary search takes Theta(log n) time in the worst case, but it would be wrong to say it always takes Theta(log n) time. If the value you want is the very first guess, the search finishes in constant time, Theta(1). The running time is never worse than Theta(log n), and it can be faster. So the honest statement is that binary search is O(log n), which allows it to be quicker on lucky inputs, while Theta(log n) would claim the lower bound holds too, which is not true for every case.

The habit to build: use O when you only have an upper bound, and use Theta when you can justify the lower bound as well.

Sometimes you want to say an algorithm takes at least a certain amount of time, without claiming anything about the top. That is what big-Omega, written Ω, is for. It is the Greek letter omega.

A running time is Ω(f(n)) when, for large enough inputs, the running time is at least k times f(n) for some positive constant k. Picture the curve of k times f sitting below the running time curve from some point onward. The algorithm might do far more work than that, but it can never do less, not once inputs get big.

Why is this useful? Because some problems force a minimum amount of work no matter how clever you are. If you must read every one of n items in a list to answer a question, your algorithm is Ω(n). Nothing can beat that, because skipping an item means you never looked at it. Omega gives you a way to say that, and it lets you prove an algorithm is optimal: if your method runs in O(n) and the problem is Ω(n), your method matches the best possible growth rate.

Together the trio works like this: O bounds from above, Ω bounds from below, and Θ does both at once. A Θ statement is really an O statement and an Ω statement sharing the same function g.

Asymptotic notation describes how an algorithm's running time grows as the input size n grows. A few habits keep you from misusing it.

Start with the simplest case: constant time. If an algorithm takes the same amount of time no matter how big the input is, it runs in Θ(1). For example, if a list is already sorted from smallest to largest and you need the minimum, the minimum sits at index 0, so you grab it in one step. The time does not grow with n at all.

Watch the wording. Saying an algorithm is O(n) is a weaker, safer claim than saying it is Θ(n), because O only caps the growth from above while Θ also pins it from below. A method that is Θ(1) on easy inputs and Θ(n) on hard ones is honestly described as O(n), since that bound holds throughout. Calling it Θ(n) would wrongly claim the n behavior happens on every input.

Also remember that asymptotic notation talks about growth rates, not stopwatch times. An O(n²) algorithm with small constants can outrun an O(n) algorithm with huge constants when n is small, because the constant multiple and the starting-size threshold are hidden inside the notation. Only as n grows does the slower growth rate always win. When you compare two algorithms for real data, check whether your n is past the crossover point or still in the small-input regime.