All of algorithms on a few pages

Use it when you need to compare two running times, prove a bound, or say which efficiency class an algorithm is in. Everything here follows Levitin Chapter 2 (§2.1–2.2), re-expressed with our own examples.

1. The three notations in one table

Let t(n) be the running time (or basic-operation count) and g(n) a simple comparison function like n².

• Θ(g) = O(g)∩Ω(g): to prove Θ, prove both directions.
• The constants c, n₀ are yours to choose. Any that work are fine; they do not have to be the smallest.
• Only large n matters. Nothing is promised for n < n₀ (that is why a Θ(n²) sort can beat a Θ(n log n) sort on small arrays).

Worked proof. Show ½n(n − 1) ∈ Θ(n²). Upper: ½n(n − 1) = ½n² − ½n ≤ ½n² for all n ≥ 0, so c₁ = ½. Lower: ½n² − ½n ≥ ½n² − ½n·½n = ¼n² once n ≥ 2, so c₂ = ¼, n₀ = 2. ∎

2. Rules you use every day

3. The limit rule — the fastest way to compare two functions

Compute

(If the limit does not exist, fall back on the definitions. That almost never happens with algorithm running times.)

L'Hôpital's rule

If t(n) → ∞ and g(n) → ∞ and the derivatives exist, then

Example — log₂ n vs. √n. Derivatives: (log₂ n)′ = 1/(n ln 2) and (√n)′ = 1/(2√n). Ratio: 2√n/(n ln 2) = 2/(ln 2·√n) → 0. So every logarithm grows slower than every square root (in fact slower than n^ε for any ε > 0).

Stirling's formula

Two consequences you will use:

• log₂ n! ∈ Θ(n log n) — this is why no comparison sort can beat n log n (Chapter 11).
• n! grows faster than aⁿ for every fixed a: lim n!/2ⁿ = ∞.

Example. Compare n! with 2ⁿ using Stirling: n!/2ⁿ ≈ √(2πn)(n/(2e))ⁿ → ∞ because n/(2e) > 1 once n > 5. ∎

4. Handy identities

• a^log_b n = n^log_b a (turns the Master Theorem's a^log_b n leaves into a power of n)
• log_b(xy) = log_b x + log_b y, log_b(x/y) = log_b x − log_b y, log_b x^k = k log_b x
• 2^log₂ n = n, and the number of bits of n is ⌊log₂ n⌋ + 1
• ⌊x⌋ ≤ x < ⌊x⌋ + 1 and ⌈x⌉ − 1 < x ≤ ⌈x⌉
• Harmonic numbers: 1 + ½ + … + 1/n = H_n ≈ ln n + 0.5772

5. The basic efficiency classes

Values below are rounded; "fits in about 1 second" assumes about 10⁸ simple operations per second.

Order from slowest-growing to fastest: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ

6. Common traps

1. Big-O is not "the worst case." O/Ω/Θ describe functions. You can give a Θ bound for the best case, the worst case or the average case separately.
2. "O(n²)" is not a promise of slowness. n ∈ O(n²) is true — just not tight. Use Θ when you mean "exactly this rate".
3. Input size is the size, not the value. For a number n, the size is b = ⌊log₂ n⌋ + 1 bits, so a loop running n times is exponential in b.
4. Drop constants only at the end. When you count operations, keep the exact sum; simplify to Θ last.
5. Don't compare exponents of different bases by eye: 4ⁿ = (2ⁿ)² is not Θ(2ⁿ).

Use it when you have turned a loop into a sum or a recursive algorithm into a recurrence and now need a closed form. The content matches what Levitin collects in Appendix A (sums) and Appendix B (recurrences), written in our own words with our own worked examples.

1. Sum formulas to know by heart

Quick checks with n = 4: S2 gives 10, S3 gives 30, S6 (with n = 3) gives 15, S7 gives 3·32 + 2 = 98 ✔.

2. Manipulation rules

• Constant factor out: ∑ c a_i = c ∑ a_i
• Split a sum of terms: ∑(a_i±b_i) = ∑ a_i±∑ b_i
• Split the range: ∑_i=l^u a_i = ∑_i=l^m a_i + ∑_i=m+1^u a_i for l ≤ m < u
• Telescoping: ∑_i=l^u(a_i − a_i−1) = a_u − a_l−1
• Shift the index: ∑_i=1ⁿ a_i−1 = ∑_j=0ⁿ⁻¹ a_j (substitute j = i − 1)
• Bounding instead of solving: ∑_i=1ⁿ f(i) ≤ n·max f; for increasing f, int₀ⁿf(x) dx ≤ ∑_i=1ⁿ f(i) ≤ int₁ⁿ⁺¹f(x) dx

3. From loops to sums (non-recursive algorithms)

Recipe (Levitin §2.3):

1. Pick the input size n.
2. Find the basic operation (usually in the innermost loop).
3. Ask whether the count depends only on n, or also on the particular input. If it varies, analyze worst, best (and average) cases separately.
4. Write the count as a sum, one ∑ per loop, using the loop's exact bounds.
5. Simplify with the formulas above; state the closed form, then the order of growth.

Example — "are all elements distinct?" by brute force.

Worst case (all distinct, or the only duplicate pair is the last one checked):

4. From recursion to recurrences

Recipe (Levitin §2.4): size → basic operation → does the count vary by input? → set up a recurrence with an initial condition → solve it (backward substitution, Master Theorem, or characteristic equation) → order of growth.

4.1 Backward substitution, step by step

1. Write the recurrence for n, then for n − 1 (or n/2), and substitute it back in.
2. Repeat two or three times until you see the pattern after i substitutions.
3. Write that general form with i.
4. Choose i so the argument hits the initial condition (for example i = n − 1, or i = k when n = 2^k).
5. Simplify with the sum formulas, then check the result on a small n.

Worked example A — Tower of Hanoi: M(n) = 2M(n − 1) + 1, M(1) = 1

Set i = n − 1: M(n) = 2ⁿ⁻¹·1 + 2ⁿ⁻¹ − 1 = 2ⁿ − 1 ∈ Θ(2ⁿ). Check: M(3) = 2·3 + 1 = 7 = 2³ − 1 ✔.

Worked example B — counting binary digits: A(n) = A(⌊n/2⌋) + 1, A(1) = 0

Solve for n = 2^k (the smoothness rule says the order of growth carries over to all n):

Set i = k: A(2^k) = A(1) + k = k, so A(n) = log₂ n ∈ Θ(log n). (The exact answer for every n is ⌊log₂ n⌋ additions; the bit count is that plus one.)

Worked example C — the exam favorite: T(n) = T(n/2) + log₂ n, T(1) = 0

This is not covered by the basic Master Theorem, because f(n) = log n is not of the form n^d. Backward substitution handles it. Let n = 2^k, so log₂ n = k:

Set i = k: T(2^k) = T(1) + 1 + 2 + … + k = k(k + 1)/2. Back in terms of n: T(n) = log₂ n (log₂ n + 1)/2 ∈ Θ(log² n). Check: T(4) = T(2) + 2 = (T(1) + 1) + 2 = 3 and 2·3/2 = 3 ✔.

Worked example D — x(n) = x(n − 1) + n, x(0) = 0

x(n) = x(n − 2) + (n − 1) + n = … = x(0) + 1 + 2 + … + n = n(n + 1)/2 ∈ Θ(n²).

4.2 Three general solutions (Levitin Appendix B, restated)

Plug f(n) = log₂ n with b = 2 into the second row: ∑_j=1^k j = k(k + 1)/2 — example C again.

5. The Master Theorem

For T(n) = a T(n/b) + f(n) with a ≥ 1, b ≥ 2 and f(n) ∈ Θ(n^d), d ≥ 0:

The same conclusions hold with O and Ω in place of Θ.

Worked examples

When it does not apply: f(n) not polynomial (like log n in example C), subproblems of unequal size (like quicksort's worst case T(n) = T(n − 1) + n), or a subtractive recurrence (T(n − 1)). Use substitution instead.

Recursion-tree picture

Draw the calls level by level. Level i has aⁱ nodes, each doing f(n/bⁱ) work, and there are log_b n levels. Add the levels. If the level sums shrink geometrically, the root wins (case 1). If they are equal, multiply by the number of levels (case 2). If they grow, the leaves win (case 3).

6. Linear recurrences with constant coefficients — the characteristic equation

For the homogeneous second-order recurrence

write the characteristic equation ar² + br + c = 0 and find its roots r₁, r₂:

Then use the two initial conditions to find α and β.

Worked example E — x(n) = 5x(n − 1) − 6x(n − 2), x(0) = 1, x(1) = 4. Characteristic equation: r² − 5r + 6 = 0, roots r₁ = 2, r₂ = 3. So x(n) = α2ⁿ + β3ⁿ. From x(0): α + β = 1. From x(1): 2α + 3β = 4. Hence β = 2, α = −1 and x(n) = 2·3ⁿ − 2ⁿ. Check: x(2) = 5·4 − 6·1 = 14 = 18 − 4 ✔.

Worked example F — Fibonacci, F(n) = F(n − 1) + F(n − 2), F(0) = 0, F(1) = 1. r² − r − 1 = 0 gives φ = (1 + √5)/2 ≈ 1.618 and φ̂ = (1 − √5)/2 ≈ −0.618, so F(n) = 1/√5(φⁿ − φ̂ⁿ) and F(n) ∈ Θ(φⁿ). Because |φ̂| < 1, F(n) is φⁿ/√5 rounded to the nearest integer.

Inhomogeneous with a constant: for x(n) = r x(n − 1) + c with r ≠ 1, add the constant particular solution p = c/(1 − r). Tower of Hanoi: M(n) = 2M(n − 1) + 1 gives p = −1, so M(n) = α2ⁿ − 1, and M(1) = 1 forces α = 1: M(n) = 2ⁿ − 1, as in example A.

Use it when you face a new problem and don't know where to start. Follow the flowchart, then copy the template for the strategy it points to. Every template below is real Forge Pseudocode: it runs in the Practice Arena and was checked by tools/check-pseudocode-snippets.mjs.

Acronyms on this page: Dynamic Programming (DP), Traveling Salesman Problem (TSP), Minimum Spanning Tree (MST), Longest Common Subsequence (LCS), Depth-First Search (DFS), Breadth-First Search (BFS), Adelson-Velsky–Landis (AVL) tree, Binary Search Tree (BST), Nondeterministic Polynomial time (NP).

1. The decision flowchart

Three questions that settle most cases

1. What is the smallest version of this problem, and how does the answer for a bigger one reuse it? (decrease, divide, DP)
2. If I take the obvious best-looking step, can I prove I never regret it? (greedy — prove it with an exchange argument, or find a counterexample on a tiny input)
3. Would the problem be trivial if the data were sorted / in a heap / in a hash table? (transform, space-time)

2. The strategies at a glance

3. Templates in Forge Pseudocode

Each template is the smallest real algorithm that shows the strategy's shape. Keep the shape, swap the details.

Brute force — check every pair

Cost: ∑_i=0ⁿ⁻²(n − 1 − i) = n(n − 1)/2 comparisons in the worst case.

Exhaustive search — try every subset

Cost: Θ(n2ⁿ). Fine for n ≤ 20, hopeless for n = 60.

Decrease-and-conquer — by one (insertion sort)

Decrease-and-conquer — by a constant factor (binary search)

Decrease-and-conquer — variable size (Euclid)

Divide-and-conquer — mergesort

Recurrence: C(n) = 2C(n/2) + (n − 1) comparisons in the worst case, so Θ(n log n) by the Master Theorem.

Transform-and-conquer — presort, then scan

Cost: Θ(n log n) for the sort + Θ(n) for the scan, instead of Θ(n²).

Space-time trade-off — distribution counting

Cost: Θ(n + (u − l)), with no key comparisons at all. Stable, because the last loop runs right to left.

Dynamic programming — coin-row

The recipe: (1) define what a table cell means in words, (2) write the recurrence, (3) find the base cases, (4) fill the table in an order where every cell's inputs are ready, (5) trace back if you need the choices.

Greedy — activity selection

Why it is safe: the activity that ends first leaves the most room for the rest (an exchange argument). With the sort, the cost is Θ(n log n).

Iterative improvement — augmenting paths (bipartite matching)

Each successful augmentation adds one matched pair; when none exists, the matching is maximum (Levitin §10.3).

Backtracking — n-queens

Branch-and-bound — knapsack with an optimistic bound

The bound prunes every branch that cannot beat the best complete solution found so far (Levitin §12.2).

4. Proof tools that go with each strategy

Use it when you need the running time of an algorithm at a glance, or want to compare two algorithms for the same job. Chapters 1–12 follow Levitin; Chapters 13–17 are the Beyond-the-textbook lessons.

How to read it. Times count the basic operation named in the lesson (key comparisons for sorting and searching, multiplications for arithmetic). "Space" is the extra memory beyond the input. In graph rows, V and E are the numbers of vertices and edges. "Stable" means equal keys keep their input order; "in place" means Θ(1) extra array memory (a recursion stack may still be used). A dash means the idea does not apply.

Acronyms: Greatest Common Divisor (GCD), Depth-First Search (DFS), Breadth-First Search (BFS), Traveling Salesman Problem (TSP), Binary Search Tree (BST), Adelson-Velsky–Landis tree (AVL), Knuth–Morris–Pratt (KMP), Dynamic Programming (DP), Longest Common Subsequence (LCS), Minimum Spanning Tree (MST), Directed Acyclic Graph (DAG), Strongly Connected Components (SCC), Longest Increasing Subsequence (LIS), Least Recently Used (LRU), input/output (I/O), Least Common Multiple (LCM), Boolean satisfiability (SAT), Nondeterministic Polynomial time (NP), First-Fit Decreasing (FFD).

Chapters 1–2 · Introduction and the analysis framework

Chapter 3 · Brute force and exhaustive search

Chapter 4 · Decrease-and-conquer

Chapter 5 · Divide-and-conquer

Chapter 6 · Transform-and-conquer

Chapter 7 · Space-time trade-offs

Chapter 8 · Dynamic programming

Chapter 9 · Greedy technique

Chapter 10 · Iterative improvement

Chapters 11–12 · Limits, and coping with them

Chapters 13–17 · Beyond the textbook

Forge Pseudocode is the Levitin-style pseudocode used in every lesson, simulation and Practice Arena problem. It is not "pretend" code: the Arena runs it, counts its operations and grades it. If you can write it on an exam, you can run it here. Every example on this page was executed by the real interpreter (docs/engine/forge-pseudo.js) with node tools/check-pseudocode-snippets.mjs.

1. The shape of an algorithm

• A program is one or more ALGORITHM Name(parameters) blocks. The first one is the entry point (the Arena calls the name given in the problem).
• Indentation defines blocks — 4 spaces per level, exactly like the book. end, endif, od, {, } lines are tolerated and ignored.
• // starts a comment. The header comments (purpose, Input, Output) are a habit worth keeping.
• A[0..n-1] in a header binds n to the array's length. A[l..r] binds l and r to the bounds the caller passed. A[1..n] gives you a 1-based view.

2. Values, assignment and arithmetic

Several statements can share a line when separated by ; — for example i ← 0; j ← n - 1.

3. Decisions

then is optional, and a short body can stay on the same line: if A[i] > m then m ← A[i].

4. Loops

5. Arrays, views and copies

• Make arrays with array(n, fill) and 2-D tables with matrix(rows, cols, fill); read cells as M[i, j] or M[i][j].
• List literals: [1, 2, 3], []. append(L, x) adds to the end; writing one past the end also extends the array.
• copy A[0..m-1] to B[0..m-1] copies element by element (Levitin's phrasing).
• length(A) works on arrays and strings.

6. Recursion and multiple results

7. Records (nodes)

A record is created with new Name; fields appear when you assign them. A field that was never assigned is null.

8. Built-in data structures

9. More built-in functions

(Top-level lines outside any ALGORITHM run first — handy for quick experiments.)

10. What the Arena counts

When you run pseudocode, the interpreter counts operations so you can check your analysis against reality:

Some problems set a budget (for example "at most n − 1 key comparisons") or a growth check (for example "must be Θ(n log n)"), so the efficiency of your solution is graded, not just its answer.

11. Friendly errors (and what they mean)