The Formal Definition of Big-Oh

In this section I make the definition of Big-Oh a little more formal, and I introduce two related notations. This is for your information only. None of it will be on an exam.

What “asymptotic” means

The word comes from asymptote, a line that a curve gets closer and closer to as the curve extends without bound. “Asymptotic” describes behavior in the limit, as the input size $n$ grows without bound ( $n \to \infty$ ).

This is what Big-Oh describes: how the work grows as the input gets large, not how much work there is for one particular input. It is also why the two rules are allowed. A constant factor and a lower-order term both change the cost at any fixed $n$ . Neither one changes how the cost grows as $n \to \infty$ . So we drop them and keep the dominant term.

The formal definition of Big-Oh

Here is the formal definition of Big-Oh: $f (n) = O (g (n))$ if there are positive constants $c$ and $n_{0}$ such that

0 \leq f (n) \leq c \cdot g (n) for all n \geq n_{0}

Here $f$ is the step count of the algorithm and $g$ is the function we write inside the $O$ . The definition says that past some input size $n_{0}$ , $f$ never goes above a constant multiple of $g$ .

Let’s check it on linear search. We counted its work as $3 n + 3$ steps, and we said it is $O (n)$ . So $f (n) = 3 n + 3$ and $g (n) = n$ . The definition asks us to find a $c$ and an $n_{0}$ such that $3 n + 3 \leq c \cdot n$ for all $n \geq n_{0}$ . Try $c = 4$ . Then we need $3 n + 3 \leq 4 n$ . Subtract $3 n$ from both sides and that is $3 \leq n$ . So the inequality holds for every $n \geq 3$ , and $n_{0} = 3$ works. We found the two constants, so $3 n + 3 = O (n)$ by the definition.

Now look at what each constant did for us. The coefficient $3$ in front of $n$ was not a problem. We picked $c = 4$ , which is bigger than $3$ , and that took care of it. Whatever the coefficient is, we can always pick $c$ larger. That is why we can suppress coefficients. The extra $+ 3$ was not a problem either. It matters for small $n$ : at $n = 1$ , $3 n + 3$ is $6$ and $4 n$ is only $4$ . But we picked $c = 4$ instead of $3$ , and that gives us one extra $n$ to spend. Once $n$ is $3$ or more, that extra $n$ is at least $3$ , which is enough to cover the $+ 3$ . That is why we can drop lower-order terms. Past some input size, the dominant term with a slightly larger constant absorbs them. These are the two rules we have been applying by hand.

Upper, lower, and tight bounds

Big-Oh is an upper bound: it says the step count grows no faster than the function inside the $O$ . There are two related notations that bound the growth in other ways.

$Ω$ , a lower bound (like $\geq$ ): $f$ grows at least as fast as $g$ . It is the same definition with the inequality flipped: $f (n) \geq c \cdot g (n)$ for all $n \geq n_{0}$ .
$Θ$ , a tight bound (like $=$ ): $f$ grows at the same rate as $g$ , meaning it is both $O (g)$ and $Ω (g)$ at once.

(There are also strict versions, little-o and little-omega, written $o (g)$ and $ω (g)$ , for “grows strictly slower” and “grows strictly faster.”)

Because $O$ is only an upper bound, saying an algorithm is $O (n^{2})$ does not mean its work grows like $n^{2}$ . It only means the work grows no faster than that. Linear search is $O (n)$ , but by the definition it is also $O (n^{2})$ and $O (2^{n})$ , since $n$ grows no faster than either of those. All three statements are true. Only the first one is useful. So in practice we always give the tightest bound we can. When we say linear search is $O (n)$ , we really mean $Θ (n)$ . Using $O$ where $Θ$ is meant is common, and this course does it too.