Asymptotic Analysis

Asymptotic analysis describes how an algorithm's resource use grows as input size $n$ becomes large. It ignores machine-specific constants when the goal is to compare growth rates, but the definitions are still precise mathematical bounds.^[1]

Prerequisites

Prerequisites: functions, inequalities, and limits.

Definition

Let $f (n)$ and $g (n)$ be nonnegative functions for all sufficiently large $n$ .
Usually $f (n)$ is running time or memory use.
Usually $g (n)$ is a simpler comparison function.

Notation

Notation	Meaning	Formal definition
$f (n) = O (g (n))$	Asymptotic upper bound	There exist constants $c > 0$ and $n_{0}$ such that $0 \leq f (n) \leq c g (n)$ for all $n \geq n_{0}$ .
$f (n) = Ω (g (n))$	Asymptotic lower bound	There exist constants $c > 0$ and $n_{0}$ such that $0 \leq c g (n) \leq f (n)$ for all $n \geq n_{0}$ .
$f (n) = Θ (g (n))$	Asymptotically tight bound	There exist constants $c_{1}, c_{2} > 0$ and $n_{0}$ such that $0 \leq c_{1} g (n) \leq f (n) \leq c_{2} g (n)$ for all $n \geq n_{0}$ .

Examples

Linear search worst-case time is $Θ (n)$ : it may inspect every item, and it never inspects more than $n$ items.
Binary search worst-case time is $Θ (\log n)$ : each comparison halves the remaining sorted search interval.
$3 n^{2} + 10 n + 7 = Θ (n^{2})$ , because constants and lower-order terms are dominated for large $n$ .
$3 n^{2} + 10 n + 7 = O (n^{3})$ is true but loose; $O$ alone does not mean "best possible."

Worked Example

Show that $5 n + 20 = Θ (n)$ .

For $n \geq 1$ :

5 n + 20 \leq 25 n,

so $5 n + 20 = O (n)$ with $c_{2} = 25$ . Also:

5 n \leq 5 n + 20,

so $5 n + 20 = Ω (n)$ with $c_{1} = 5$ . Since both bounds hold, $5 n + 20 = Θ (n)$ .

Common Mistakes

Saying Big-O means exact runtime; it is only an upper bound.
Writing $O (2 n)$ instead of simplifying to $O (n)$ .
Treating $Ω$ like "best case"; it is lower-bound notation, not automatically one case label.
Ignoring the phrase "for all sufficiently large $n$ ."
Comparing algorithms only by asymptotic order when constants or input sizes dominate in practice.

Connections

Related note	Use
Learning Paths	Navigation hub

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 3rd ed., MIT Press, ISBN 978-0-262-03384-8. ↩︎