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

Before we begin, one reminder of the ladder we are matching every answer to:

O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)

Here < means "grows strictly slower once n is large".

Figure s01 (below): the growth ladder. The horizontal axis is the input size n; the vertical axis is the number of steps $T (n)$ , drawn on a logarithmic scale so that all eight rungs fit on one picture. Eight curves are drawn, one per class — flat $O (1)$ , slowly-rising $O (lo g n)$ , straight $O (n)$ , slightly-steeper $O (n lo g n)$ , bending $O (n^{2})$ , steeper $O (n^{3})$ , and the two runaway curves $O (2^{n})$ (dashed) and $O (n!)$ (dotted). The key thing to read off the picture: each curve eventually rises above every curve below it and never dips back — that is exactly what the < chain means, and the two topmost curves ( $2^{n}$ then $n!$ ) shoot off the top the fastest.

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

Level 1 — Recognition

(You are handed a growth pattern; name its class. No arithmetic tricks yet.)

L1.1

An algorithm always looks at exactly the first 3 elements of an array, no matter how long the array is. What is its complexity?

Recall Solution

WHAT the code does: touches a fixed number of elements — three — forever. WHY that fixes the class: the step count never grows with n. Plotting "work vs n" gives a flat horizontal line — the flat line sitting at height 1 in figure s01. Answer: $O (1)$ — constant.

L1.2

Each iteration of a loop triples the value of a counter (c = c * 3) starting from 1 until it reaches n. How many iterations?

Recall Solution

WHAT: the counter goes $1, 3, 9, 27, \dots$ i.e. $3^{k}$ after k steps. WHY log: it stops at the first k with $3^{k} \geq n$ , so $k = ⌈ lo g_{3} n ⌉$ (using the ceiling defined above, because the iteration count must round up to a whole number). Multiplying by a constant factor each step is the signature of a logarithm (not subtracting). WHY the base drops: $lo g_{3} n = \frac{lo g _{2} n}{lo g _{2} 3}$ — a constant multiple — and Big-O throws constants away. Answer: $O (lo g n)$ .

L1.3

A function makes a take-or-skip binary choice for each of n items and explores every combination. What is its complexity?

Recall Solution

WHAT: n independent binary choices → $2 \times 2 \times \dots \times 2$ ( $n$ twos) $= 2^{n}$ combinations. WHY exponential: each new item doubles the number of paths — the steeply-rising dashed curve in figure s01 that overtakes the parabola. Answer: $O (2^{n})$ .

Level 2 — Application

(Now you count steps with the summation and nesting rules.)

L2.1

for i in range(n):
    for j in range(n):
        do_constant_work()

Give the exact step count and its Big-O.

Recall Solution

WHAT: the inner loop runs n times, and it runs once for each of the n outer iterations. WHY multiply: nested loops multiply because the inner work repeats fully inside every outer pass. $steps = \sum_{i = 1}^{n} n = n \cdot n = n^{2} .$ Answer: $n^{2}$ steps $= O (n^{2})$ .

L2.2

for i in range(n):        # loop A
    work()
for j in range(n):        # loop B
    work()

Big-O?

Recall Solution

WHAT: two loops one after the other, not one inside the other. WHY add: sequential loops add their work: $n + n = 2 n$ . WHY drop the 2: Big-O ignores constant factors → $O (2 n) = O (n)$ . Answer: $O (n)$ .

L2.3

for i in range(n):
    for j in range(i, n):     # starts at i, not 0
        do_constant_work()

Compute the exact number of inner calls and the Big-O.

Recall Solution

WHAT: when the outer index is i, the inner loop runs $n - i$ times. WHY this sum: total $= \sum_{i = 0}^{n - 1} (n - i) = n + (n - 1) + (n - 2) + \dots + 1$ . WHY the two sums are equal: substitute $k = n - i$ . When $i = 0$ , $k = n$ ; when $i = n - 1$ , $k = 1$ ; and as $i$ steps up by 1, $k$ steps down by 1. So the list of values $n - i$ is just the numbers $1, 2, \dots, n$ written backwards: $\sum_{i = 0}^{n - 1} (n - i) = \sum_{k = 1}^{n} k .$ WHY that sum equals $\frac{n ( n + 1 )}{2}$ (Gauss's pairing): write the sum forwards and backwards and add them column by column:

1 n + + 2 (n - 1) + \dots + + \dots + n 1

Every column sums to $n + 1$ , and there are $n$ columns, so twice the sum is $n (n + 1)$ , giving $\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2}$ . WHY still $O (n^{2})$ : expand $\frac{n ( n + 1 )}{2} = \frac{n ^{2}}{2} + \frac{n}{2}$ ; the $n^{2}$ term dominates and the $\frac{1}{2}$ is a constant. Answer: $\frac{n ( n + 1 )}{2}$ calls $= O (n^{2})$ .

Figure s02 (below): the triangle of work. A grid of shaded squares, one square per inner-loop call. Row i=0 (drawn at the top) is fully shaded across all n columns; row i=1 is one square shorter; each lower row loses one more square, so the shaded region forms a right triangle. Counting the squares in the triangle is the sum $\sum_{k = 1}^{n} k$ ; its area — half of the full $n \times n$ square — is why the count is $\approx \frac{n ^{2}}{2}$ and the class is $O (n^{2})$ .

Level 3 — Analysis

(Messy, mixed, or deceptive code — you must reason, not pattern-match.)

L3.1

for i in range(n):
    j = n
    while j > 1:
        j = j // 2       # floor division: keep the whole part

Big-O?

Recall Solution

WHAT the inner loop does: using floor division (//, defined at the top of this page), j steps through $n, ⌊ n /2 ⌋, ⌊ n /4 ⌋, \dots$ down to 1 — roughly $lo g_{2} n$ halvings. WHAT the outer loop does: runs n times, and the inner $lo g n$ work happens fully inside each pass. WHY multiply: nested → multiply: $n \times lo g_{2} n$ . Answer: $O (n lo g n)$ .

L3.2

i = 1
while i < n:
    do_constant_work()
    i = i * 2

Big-O? Then: what if the last line were i = i + 2?

Recall Solution

Case i = i*2: after $k$ iterations $i = 2^{k}$ ; the loop stops the moment $2^{k} \geq n$ , i.e. $k = ⌈ lo g_{2} n ⌉$ steps (ceiling, since the count rounds up to a whole number) → $O (lo g n)$ . Case i = i+2 — done carefully: after $k$ iterations the counter is $i = 1 + 2 k$ (it starts at 1 and adds 2 each pass). The loop keeps going while $i < n$ , so the last iteration that still runs is the largest $k$ with $1 + 2 k < n$ . Solve for $k$ : $1 + 2 k < n \Rightarrow 2 k < n - 1 \Rightarrow k < \frac{n - 1}{2} .$ Since $k$ must be a whole number, the number of iterations is $⌈ \frac{n - 1}{2} ⌉$ (the count of integers $k = 0, 1, 2, \dots$ satisfying the strict inequality; the ceiling rounds up to include the partial step). WHY that's $O (n)$ : $⌈ \frac{n - 1}{2} ⌉ \approx \frac{n}{2}$ ; the ceiling changes the count by at most 1 and the $\frac{1}{2}$ is a constant factor — both dropped by Big-O. WHY the huge gap: multiplying by a factor is the log signature; adding a constant is the linear signature. Same target n, totally different classes. Answer: $O (lo g n)$ vs $O (n)$ .

L3.3

Three separate blocks run in sequence:

Block A: a single nested double loop → $O (n^{2})$
Block B: a merge-sort call → $O (n lo g n)$
Block C: one pass over the array → $O (n)$

What is the total complexity?

Recall Solution

WHY add: the blocks run one after another (sequential) → add their costs: $O (n^{2}) + O (n lo g n) + O (n) .$ WHY keep only $n^{2}$ : for large n, $n^{2} ≫ n lo g n ≫ n$ . The biggest term swallows the rest. Answer: $O (n^{2})$ .

Level 4 — Synthesis

(Turn recurrences and problem descriptions into a class from scratch — see Recurrence-Relations and Master-Theorem.)

L4.1

A recursive algorithm satisfies $T (n) = 2 T (n /2) + c n$ with $T (1) = c$ . Derive its Big-O by unrolling the recursion tree.

Recall Solution

WHAT the recurrence says: solve two half-sized subproblems, then do $c n$ merging work. WHY a tree: each call spawns 2 children of size $n /2$ ; those spawn 4 of size $n /4$ ; and so on. Work per level: the top level does $c n$ . The next level: two nodes each doing $c (n /2)$ → total $c n$ again. Every level does $c n$ because the pieces shrink but there are proportionally more of them. Number of levels — counted precisely: the sizes go $n, n /2, n /4, \dots, 1$ . Reaching size 1 from size $n$ by repeated halving takes $lo g_{2} n$ halvings, but we must count the levels (the rows of the tree), and there is a row before the first halving. So the levels are: level 0 (size $n$ ), level 1 (size $n /2$ ), …, level $lo g_{2} n$ (size 1) — that is $lo g_{2} n + 1$ rows in total. What if n is NOT a power of two? Then the halves are not exact — a real implementation splits into pieces of size $⌊ n /2 ⌋$ and $⌈ n /2 ⌉$ (floor and ceiling, defined at the top). The tree depth is then $⌈ lo g_{2} n ⌉$ instead of an exact integer, and the per-level work is still at most $c n$ . Rounding shifts the count by at most a constant, so the class is unchanged: $O (n lo g n)$ . (This is exactly why the Master-Theorem states its result for general n, not just powers of two.) Total: $(work per level) \times (levels) = c n \cdot (lo g_{2} n + 1) = c n lo g_{2} n + c n$ . WHY the $+ 1$ vanishes in Big-O: $c n lo g_{2} n + c n$ — the $c n lo g_{2} n$ term dominates and the extra $c n$ is a lower-order term, dropped. Answer: $O (n lo g n)$ — this is exactly Merge-Sort.

L4.2

A recurrence is $T (n) = 2 T (n - 1) + c$ with $T (0) = c$ . Unroll it and give the Big-O.

Recall Solution

WHY this differs from L4.1: here the subproblem shrinks by subtracting 1 (not halving), and there are two of them each time — so the count doubles at every level while depth stays n. Unroll one layer at a time:

T (n) = 2 T (n - 1) + c = 2 (2 T (n - 2) + c) + c = 2^{2} T (n - 2) + 2 c + c = 2^{2} (2 T (n - 3) + c) + 2 c + c = 2^{3} T (n - 3) + 2^{2} c + 2 c + c .

The pattern: after peeling $k$ layers, $T (n) = 2^{k} T (n - k) + c (2^{k - 1} + \dots + 2 + 1)$ . Set $k = n$ to hit the base case $T (0) = c$ : $T (n) = 2^{n} T (0) + c \sum_{i = 0}^{n - 1} 2^{i} .$ WHY $\sum_{i = 0}^{n - 1} 2^{i} = 2^{n} - 1$ (the geometric-series step): call the sum $S = 1 + 2 + 4 + \dots + 2^{n - 1}$ . Double it: $2 S = 2 + 4 + \dots + 2^{n}$ . Subtract: $2 S - S = 2^{n} - 1$ (every middle term cancels), so $S = 2^{n} - 1$ . Substitute ( $T (0) = c$ ): $T (n) = 2^{n} c + c (2^{n} - 1) = 2^{n + 1} c - c .$ The $2^{n + 1} c$ term is a constant multiple of $2^{n}$ . Answer: $O (2^{n})$ — naive recursive Fibonacci lives here.

L4.3

You must generate every ordering of n distinct items to test each one. What is the complexity, and why is it worse than $O (2^{n})$ ?

Recall Solution

WHAT: the number of orderings (permutations) of n items is $n! = n \cdot (n - 1) \dots 1$ . WHY worse than $2^{n}$ : compare factor-by-factor. Both are products of n numbers: $n! = 1 \cdot 2 \cdot 3 \dots n, 2^{n} = 2 \cdot 2 \cdot 2 \dots 2.$ In $n!$ every factor from 3 onward exceeds 2, so $n!$ pulls ahead. Checking the crossover directly: at $n = 3$ , $n! = 6$ but $2^{n} = 8$ (so $2^{n}$ still leads); at $n = 4$ , $n! = 24 > 16 = 2^{n}$ . So $n!$ overtakes $2^{n}$ starting at $n = 4$ and never looks back. Answer: $O (n!)$ .

Level 5 — Mastery

(Subtle judgement calls where the "obvious" asymptotic answer is a trap.)

L5.1

For n = 10, which is larger: $n^{2}$ or $2^{n}$ ? For n = 3?

Recall Solution

n = 10: $n^{2} = 100$ , $2^{n} = 1024$ → $2^{n}$ is larger. n = 3: $n^{2} = 9$ , $2^{n} = 8$ → $n^{2}$ is larger. WHY the crossover: $2^{n}$ starts below $n^{2}$ for tiny n but its doubling overtakes near $n \approx 4$ and then explodes. Asymptotic order ( $2^{n}$ eventually wins) says nothing about small n. Answer: $2^{n}$ at n=10; $n^{2}$ at n=3.

L5.2

Algorithm P is $O (n lo g n)$ with a huge hidden constant (say $1000 n lo g_{2} n$ operations). Algorithm Q is $O (n^{2})$ with a tiny constant ( $n^{2}$ operations). Below roughly what n does the "worse" quadratic algorithm actually run fewer operations?

Recall Solution

WHAT we compare: we want the values of n where Q is cheaper, i.e. where $n^{2} < 1000 n lo g_{2} n .$ Simplify: divide both sides by n (positive, so the inequality direction is safe): $n < 1000 lo g_{2} n .$ Q is cheaper exactly while n stays below the value where the two sides are equal. Bracket the crossover by testing values:

at $n = 10000$ : $lo g_{2} 10000 \approx 13.29$ , so $1000 \cdot 13.29 \approx 13288 > 10000$ → right side bigger → Q wins.
at $n = 20000$ : $lo g_{2} 20000 \approx 14.29$ , so $1000 \cdot 14.29 \approx 14288 < 20000$ → left side bigger → P wins. So the crossover sits between $10000$ and $20000$ . Narrowing further (solving $n = 1000 lo g_{2} n$ numerically) lands near $n \approx 13750$ . WHY this happens: Big-O hides constants; a large enough constant keeps the "slower" class cheaper until n grows past the crossover. Answer: for n up to roughly $1.4 \times 1 0^{4}$ (crossover near $n \approx 13750$ ) the $O (n^{2})$ algorithm does fewer operations; beyond that the $O (n lo g n)$ one wins.

L5.3

An algorithm runs $O (n^{2})$ in the worst case but $O (n)$ on already-sorted input. A colleague reports it as "an $O (n)$ algorithm." Are they right? Which class label is honest, and why does this connect to 3.1.03-Best-Worst-Average-Case?

Recall Solution

WHAT is going on: the running time depends on the shape of the input, not just its size — best case $O (n)$ , worst case $O (n^{2})$ . WHY "O(n)" is misleading: unless the input is guaranteed sorted, the honest guarantee is the worst case, $O (n^{2})$ . Reporting only the best case hides the failure mode. The nuance: both labels are true statements about different cases. State which case you mean (this is exactly the best/worst/average distinction). Answer: The honest headline is $O (n^{2})$ (worst case); $O (n)$ is only the best case. Always name the case.

Flashcards

Tripling a counter each step until it reaches n costs what?

O (lo g n)

— multiplying by a constant factor is the log signature.

Two loops in sequence, each O(n) — total?

O (n)

— sequential loops add (

2 n

), constant dropped.

Exact call count of the triangular loop for j in range(i, n)?

\frac{n ( n + 1 )}{2} = O (n^{2})

Outer loop n times, inner loop halving n each pass — total?

O (n lo g n)

— nested, so

n \times lo g n

Solve

T (n) = 2 T (n - 1) + c

O (2^{n})

— branching factor 2 over depth n; geometric sum

\sum_{i = 0}^{n - 1} 2^{i} = 2^{n} - 1

Why is O(n!) worse than O(2ⁿ)?

n!

is a product of n factors most exceeding 2; overtakes

2^{n}

from n=4.

At n=3, which is larger, n² or 2ⁿ?

n^{2} = 9 > 2^{n} = 8

; the crossover is near n≈4.

Can an O(n²) algorithm beat an O(n log n) one?

Yes, for small n or when the n log n algorithm has a huge hidden constant.

Sum of blocks O(n²)+O(n log n)+O(n) is?

O (n^{2})

— the largest term dominates a sum.

What do floor ⌊x⌋ and ceiling ⌈x⌉ mean?

Floor rounds down to the nearest integer ≤ x; ceiling rounds up to the nearest integer ≥ x.