Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!): Foundations

This page assumes nothing. Every letter, every squiggle the parent note uses — we build it here from the ground up, in the order that each one needs the one before it. When you finish, re-read the parent note (the parent topic) and every symbol will already be familiar.

1. `n` — the size of the input

Why does the topic need n? Because complexity is never a single number. "This algorithm takes 40 steps" is useless — 40 steps for how much input? We always ask: as n gets bigger, what happens to the work? So n is the knob we turn, and everything else describes what happens when we turn it.

Figure — Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!)

2. `T(n)` — the work as a function of `n`

The whole subject is really the study of the shape of T(n) — does it stay flat, climb gently, or shoot up like a rocket?

3. Exponents: `n²`, `n³`, and what a small raised number means

Why the topic needs this: a nested loop — a loop inside a loop — touches every pair of items. If the outer loop runs n times and, for each of those, the inner loop also runs n times, the total is $n \times n = n^{2}$ . The square grid in the figure is that pair-counting. Three nested loops fill a cube: $n^{3}$ .

4. Powers of 2: `2ᵏ` and `2ⁿ` — repeated doubling

Why does the topic care? Two reasons, and they are mirror images:

Doubling upward ( $2^{n}$ ): if every new item forces a keep-or-toss choice, the number of combinations doubles with each item. n items → $2^{n}$ combinations. This is where the "exponential" wall comes from.
Halving downward (leads to log, next section): if each step throws away half the data, you are running the doubling tree in reverse.

5. The logarithm: `log₂ n` — "how many halvings?"

Powers of 2 answer: "I doubled k times — how big did I get?" The logarithm answers the exact reverse question.

6. Summation: `∑` — "add up a whole list of things"

7. Big-O: `O(...)` — the growth label

Now the crown symbol of the whole topic.

Definition What

O(f(n)) means — plainly, then formally Plainly: O(...) (read "Big-O of…") is a label for how fast T(n) grows as n gets large — ignoring constant multipliers and smaller side-terms. Saying an algorithm is $O (n^{2})$ means: for big n, its work grows like n², give or take a constant factor. Formally: we write $T (n) = O (f (n))$ when there exist two fixed positive numbers — a constant c and a threshold $n_{0}$ — such that $T (n) \leq c \cdot f (n) for every n \geq n_{0} .$ In words: past some starting point $n_{0}$ , the curve T(n) never rises above a scaled copy $c \cdot f (n)$ of the reference curve. The c absorbs the constant factor we chose to ignore; the $n_{0}$ says "we only promise this for large enough n". Picture: a family of curves on a graph. Big-O says "past $n_{0}$ , your T(n) curve stays under $c \cdot f (n)$ ."

8. `<` and `≪` between growth classes

Definition What

≪ means here — and how it differs from numeric < Ordinary < compares two numbers: 3 < 5 is a fact about those two values. Between complexity classes, though, < (and its emphatic cousin ≪, "much less than") compares growth rates, not single values. Writing $n ≪ 2^{n}$ means "for large enough n, 2ⁿ leaves n hopelessly behind, and the gap only widens." How to read/formalise it: $f (n) ≪ g (n)$ (equivalently " $f$ grows strictly slower than $g$ ") is just Big-O with a one-way twist — $f (n) = O (g (n))$ but $g (n) \neq = O (f (n))$ . So the class-level < is really a statement about Big-O, whereas the numeric < is about two plain numbers. When you see < between formulas like $n^{2} < 2^{n}$ in a growth ladder, read it as "the left class is eventually dwarfed by the right", not "true at every single n" (indeed $n^{2} > 2^{n}$ for n = 3). Picture: two curves; past some crossing point the faster one rockets up and never comes back down to the slower one.

That is exactly the meaning inside the parent note's ladder $1 ≪ lo g n ≪ n ≪ n lo g n ≪ n^{2} ≪ n^{3} ≪ 2^{n} ≪ n!$ — each class is eventually dwarfed by the next.

9. Factorial: `n!` — every possible ordering

The prerequisite map

Read it top to bottom: n seeds everything; exponents, doubling, and halving give the shapes; summation and Big-O let us label a piece of code with a shape; the ladder orders the shapes — and that is the topic.

Equipment checklist

Cover the right side and answer out loud. If any one stumps you, re-read its section above before opening the parent note.

What does the letter n stand for, and what values may it take?

The size of the input — a non-negative whole number (

0, 1, 2, \dots

); n = 0 means empty input.

Read T(n) in plain words.

"T of n" — the number of basic steps the algorithm takes for an input of size n.

What does the exponent in n² count?

How many copies of n are multiplied together — here two, so

n \times n

What does 2^k mean, what values may k take, and what real process does it picture?

Multiply k twos together (k a non-negative whole number,

2^{0} = 1

); it pictures repeated doubling.

log₂ n answers which question, and for which values of n is it defined?

"To what power must I raise 2 to get n?"; defined only for

n \geq 1

(no power of 2 equals 0), with

lo g_{2} 1 = 0

What does

⌈ x ⌉

mean, and why do step counts use it?

"Ceiling of x" — round x up to the nearest whole number at or above it; step counts must be whole steps, so a fractional formula rounds up.

How many halvings does a non-power-of-two n need?

⌈ lo g_{2} n ⌉

— round the log up, since the last partial cut still costs a full step.

What does the summation index i range over, and what is an empty sum?

i steps through whole numbers from bottom to top; if the range is empty the sum is 0.

What is

\sum_{i = 1}^{n} i

in closed form?

\frac{n ( n + 1 )}{2}

, which grows like

n^{2}

What does the class O(1) mean and what does its curve look like?

Constant time — work independent of n, a fixed bounded number of steps; its curve is a flat horizontal line.

State the formal definition of

T (n) = O (f (n))

There exist constants

c > 0

and

n_{0}

with

T (n) \leq c \cdot f (n)

for all

n \geq n_{0}

When we write

n ≪ 2^{n}

, are we comparing numbers or growth rates, and how does that differ from numeric <?

Growth rates:

n = O (2^{n})

but not vice versa; numeric < compares two plain values, class < compares eventual growth.

What does n! count, what is

0!

, and why does it beat 2ⁿ?

Orderings of n items;

0! = 1

(one way to arrange nothing); most of its factors exceed 2, so it overtakes

2^{n}

from n = 4.