Textbook
As $n\in\mathbb N$ tends to infinity, the functions eventually satisfy $f(n)\ge0$ and $g(n)>0$. The statement $f\in O(g)$ means that constants $C>0$ and $n_0$ exist such that $f(n)\le Cg(n)$ for every $n\ge n_0$. This is an upper growth bound.
The multiplier $C$ and threshold $n_0$ are fixed once, independently of $n$. A finite initial set of exceptions is allowed; continually changing the multiplier is not. For $f(n)=3n+7$, suitable constants are $C=10$ and $n_0=1$, because $3n+7\le10n$ whenever $n\ge1$.
The class $O(g)$ contains functions bounded by a constant multiple of $g$. The common $f(n)=O(g(n))$ abbreviates class membership rather than symmetric numerical equality. An upper bound need not be tight: $3n+7\in O(n^2)$ also holds.
For an algorithm, the input size, operation model, and analyzed case must be specified first. Bounds can describe worst-case, best-case, or another chosen running-time function; O itself does not mean “worst case.” Additional memory requires a separate analysis.
For the chosen nonnegative functions with $g(n)>0$, the condition says that $f(n)/g(n)$ is bounded above on some eventual tail. Refuting a proposed bound means showing that no fixed multiplier can contain that ratio. For example, $n^2$ is not in $O(n)$: $n^2\le Cn$ would imply $n\le C$, which fails once $n$ is sufficiently large. The multiplier cannot grow with the input.
Definitions and notation: Mathematics for Computer Science.
Related concepts: Big Theta: a tight growth order, Little o: negligible relative growth.
In plain language
An upper bound resembles a ceiling containing the entire cost curve beyond some threshold. A constant multiplier can raise the ceiling, but it cannot be rebuilt for each new input. Linear costs also fit under a quadratic ceiling, so a valid bound may be unnecessarily loose. “The rent is below a national budget” can be honest without helping an apartment search: big O bounds growth rather than stating exact running time.
Example
The constructed function $f(n)=3n+7$ counts abstract operations. The same ceiling $10n$ is tested as the input grows.
Big O: an upper growth bound
Input 1
At n = 1 the function touches the ceiling.
Step 1 of 4: Input 1
Read all steps
Input 1
At n = 1 the function touches the ceiling.
- n; f(n); 10n
- 110included10current
Input 2
The multiplier stays 10; the function is below the ceiling.
- n; f(n); 10n
- 213included20current
Input 10
The same constant multiplier works at a larger input.
- n; f(n); 10n
- 1037included100current
All later inputs
Since 7 ≤ 7n for n ≥ 1, the bound holds for every such n.
- C; n₀
- 10included1included
The first three states check numbers: 10, 13, and 37 do not exceed 10, 20, and 100. The final state explains why the agreement continues. For $n\ge1$, the extra 7 is at most $7n$, letting both linear parts combine into $10n$. The multiplier 10 deliberately leaves room to spare; class membership does not require finding the smallest possible multiplier.
The table checks examples; the final inequality establishes the bound for the entire tail.