Big-O Notation

Do not panic at the messy bounds. Count the loops: there are four, nested one inside the other, and each one runs a number of times that is at worst proportional to n. Every extra nested loop that ranges up to about n multiplies the total count by another factor of about n, so four of them give roughly n × n × n × n = n⁴. The exact starting points shift the constant in front but not the shape.

The clean test is to count the increments and double n. If it is really n⁴, doubling n should multiply the count by about 2⁴ = 16:

def prestiferous(n):
    r = 0
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            for k in range(j, i + j + 1):
                for l in range(1, (i + j - k) + 1):
                    r += 1
    return r

prev = None
for n in [5, 10, 20, 40, 80]:
    r = prestiferous(n)
    ratio = "-" if prev is None else f"{r / prev:.2f}x"
    print(f"n={n:>3}  r={r:>12,}  ratio={ratio}")
    prev = r

The ratio climbs steadily towards 16 — the unmistakable fingerprint of n⁴. (It approaches 16 from below rather than sitting on it exactly because of the lower-order terms, just as the doubling harness behaved in weeks 5–7.)

Optional challenge: the exact closed form can be worked out with the summation techniques of §8.16's later problems, but the marks are for the class, not the formula.

Answer: peeling the loops from the inside gives the exact value r = n(n+1)(n+2)(3n+1)/24, so the running time is Θ(n⁴). (The loop depth only hints at the class; summing the loops proves it.)

Again, ignore the awkward starting points and count the loops: three, nested, each ranging over a stretch that is at worst about n long. Three nested loops over roughly n give about n³. The inner bounds depending on i and j only shrink the count by a constant fraction — they cannot change the power of n. If it is cubic, doubling n should multiply the count by about 2³ = 8:

def conundrum(n):
    r = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            for k in range(i + j - 1, n + 1):
                r += 1
    return r

prev = None
for n in [10, 20, 40, 80, 160]:
    r = conundrum(n)
    ratio = "-" if prev is None else f"{r / prev:.2f}x"
    print(f"n={n:>3}  r={r:>10,}  ratio={ratio}")
    prev = r

The ratio settles towards 8 — cubic confirmed by arithmetic, no stopwatch needed.

Answer: the moving start points empty many iterations, leaving the exact count r = Σi=1⌊n/2⌋ (n−2i+1)(n−2i+2)/2 (a closed form m(m+1)(4m−1)/6 for even n = 2m), so the worst-case running time is Θ(n³). Depth alone would not prove this — the ranges must be summed.

Θ(n³) means "sandwiched between two constant multiples of n³ once n is large". The clean trick is to divide the whole expression by n³ and watch what happens as n grows:

(n³ − 3n² − n + 1) / n³ = 1 − 3/n − 1/n² + 1/n³

Each of the trailing fractions heads to 0 as n grows, so the whole ratio heads to 1. That means for large enough n the expression is close to n³ — certainly between, say, 0.5 n³ and 1 · n³. A quick check: at n = 10 the value is 1000 − 300 − 10 + 1 = 691, and indeed 0.5(1000) = 500 ≤ 691 ≤ 1000. Two constant multiples of n³ trap it, which is exactly the definition of Θ(n³).

Answer: Θ(n³).

This is the headline fact of the ladder: an exponential eventually overtakes any polynomial and never looks back. To prove n² = O(2ⁿ) we just need one constant c and a starting point n₀ such that n² ≤ c · 2ⁿ for all n ≥ n₀. Watch the two race:

At n = 3 the polynomial is briefly ahead (9 > 8), but from n = 4 onward 2ⁿ catches up and then pulls away for good — at n = 10 it is already ten times larger, and the gap only widens. So with c = 1 and n₀ = 4 we have n² ≤ 2ⁿ for all n ≥ 4, which is exactly what O demands.

Answer: n² = O(2ⁿ), witnessed by c = 1, n₀ = 4.

These are the rules that let us analyse code one piece at a time — price each region, then add or multiply — so they are worth seeing once. "f = O(g)" just means there is a constant c with f ≤ c · g for large n. So write f₁ ≤ c₁ g₁ and f₂ ≤ c₂ g₂.

Sum (2-13). Add the two inequalities: f₁ + f₂ ≤ c₁ g₁ + c₂ g₂. Let c be the bigger of c₁ and c₂; then the right side is at most c(g₁ + g₂). So f₁ + f₂ = O(g₁ + g₂). This is why sequential blocks of code add up, and keeping the biggest is just simplifying the sum.

Product (2-15). Multiply the two inequalities (all quantities positive): f₁ · f₂ ≤ c₁ c₂ · g₁ · g₂. The single constant c₁ c₂ does the job, so f₁ f₂ = O(g₁ g₂). This is why a loop that runs O(g₁) times doing O(g₂) work each time costs the product.

Ω versions (2-14). Identical argument with the inequalities flipped: f ≥ c · g. Adding lower bounds gives a lower bound on the sum; multiplying lower bounds gives a lower bound on the product. So both rules hold for Ω too — and since Θ is just O and Ω together, they hold for Θ as well.

Answer: both rules hold; they are the formal licence for the "add sequential parts, multiply nested loops" recipe from §8.5.

This is the formal version of "keep the highest power". Every term ai ni with i ≤ k satisfies |ai ni| ≤ |ai| nk once n ≥ 1, because a lower power of n is no larger than the top power. Add the terms up:

|a_k n^k + … + a₀| ≤ (|a_k| + … + |a₀|) · n^k

The bracket c = |ak| + … + |a0| is a fixed constant — it does not depend on n. So the whole polynomial is at most c · nk, which is precisely O(nk).

Answer: O(nk), with the constant being the sum of the absolute values of the coefficients.

Intuition first: when n is large, adding a fixed number a barely nudges it — 1 000 000 + 7 is, for growth purposes, still a million. So (n + a) and n grow at the same rate, and raising both to the same power b keeps them at the same rate. Formally, look at the ratio:

(n + a)ᵇ / nᵇ = (1 + a/n)ᵇ → 1^b = 1  as n → ∞

Because that ratio approaches 1, for large n it stays trapped between two fixed constants (say between ½ and 2). That traps (n + a)ᵇ between ½ nᵇ and 2 nᵇ — the sandwich that defines Θ.

Answer: (n + a)ᵇ = Θ(nᵇ).

Tidy each into its shape first: n−n3+7n5 → n5; n2+lg n → n2 (ties with n2); ln n ties lg n; 2n−1 = ½·2n ties 2n; en is above 2n (since e>2); and n1+ε sits between n lg n and n2. Then walk the ladder — remembering any real power of n beats any power of a logarithm.

Answer (braces = ties): lg lg n < {ln n = lg n} < (lg n)2 < √n < n < n lg n < n1+ε < {n2 = n2+lg n} < n3 < n5 < {2n−1 = 2n} < en < n!

The traps: (1/3)n shrinks to 0 (smallest of all); 6 is a constant; and the sneaky pair (log n)2 vs n1/3 — a squared logarithm is still a logarithm, and any real power of n (even 1/3) eventually wins, so (log n)2 < n1/3. Also n/log n sits just below n, and (3/2)n < 2n.

Answer (braces = ties): (1/3)n < 6 < log log n < {log n = ln n} < (log n)2 < n1/3 < √n < n/log n < n < n log n < {n2 = n2+log n} < n3 < n5 < (3/2)n < 2n < n!

(a) f = o(g) and f ≠ Θ(g). Easy: take f = n, g = n². n grows strictly slower than n² (so little-o holds), and they are not the same rate (so not Θ). In fact little-o always rules out Θ, so any little-o example works.

(b) f = Θ(g) and f = o(g). Impossible. Θ says "same rate"; little-o says "strictly slower". A function cannot be both exactly as fast and strictly slower than another. No such pair exists.

(c) f = Θ(g) and f ≠ O(g). Impossible. Θ is O and Ω together, so f = Θ(g) already forces f = O(g). You cannot have the first without the second.

(d) f = Ω(g) and f ≠ O(g). Easy: take f = n², g = n. n² grows at least as fast as n (Ω holds), but it is not bounded above by n (so not O). This is the usual picture of a strict lower bound.

Answer: (a) e.g. n, n² · (b) none · (c) none · (d) e.g. n², n.

(a) ∑ 1/i. This is the harmonic number, and it is famously ≈ ln n — add the terms up and they creep towards the natural log. So it is Θ(log n). A quick numerical check confirms the gap Hₙ − ln n settles at a constant (about 0.577, Euler's constant):

import math
for n in [10, 100, 1000, 10000]:
    H = sum(1.0 / i for i in range(1, n + 1))
    print(f"n={n:>6}  H={H:.4f}  ln n={math.log(n):.4f}  gap={H - math.log(n):.4f}")

The gap stops moving, which means H and ln n stay a constant apart — the signature of Θ(log n).

(b) ∑ ⌈1/i⌉. For every i ≥ 1, the value 1/i lies in (0, 1], so its ceiling ⌈1/i⌉ is exactly 1. Adding 1 a total of n times gives n. So the sum is Θ(n).

(c) ∑ log i. Summing logs is the log of the product: ∑ log i = log(1 · 2 · … · n) = log(n!), which is Θ(n log n) (see part d).

(d) log(n!). Half of the n factors are at least n/2, so n! is at least (n/2)n/2, giving log(n!) ≥ (n/2) log(n/2) — on the order of n log n. And n! is at most nn, giving log(n!) ≤ n log n. Trapped both sides: Θ(n log n).

Answer: (a) Θ(log n) · (b) Θ(n) · (c) Θ(n log n) · (d) Θ(n log n).

Two facts do all the work. A sum of n terms whose largest is a power iᵇ behaves like Θ(nᵇ⁺¹) (n copies of the top term, roughly). And a geometric sum — each term a fixed multiple of the last, like 4ⁱ — is dominated by its final term, so it is Θ of that last term.

(a) ∑ (3i⁴ + 2i³ − 19i + 20). The top piece is i⁴, and ∑ i⁴ = Θ(n⁵). So Θ(n⁵).

(b) ∑ (3 · 4ⁱ + 2 · 3ⁱ − i¹⁹ + 20). The geometric 4ⁱ term outgrows everything, and a geometric sum is Θ of its last term 4ⁿ. So Θ(4ⁿ).

(c) ∑ (5i + 3 · 2ⁱ). The geometric 2ⁱ term dominates the linear one; the sum is Θ of its last term. So Θ(2ⁿ).

Answer: (a) Θ(n⁵) · (b) Θ(4ⁿ) · (c) Θ(2ⁿ).

A geometric series sums to S = 3 + 3² + … + 3ⁿ = (3n+1 − 3) / 2, which is about 3n+1/2. The whole thing is dominated by its last term, so S = Θ(3ⁿ).

Now the trick: 3n−1, 3ⁿ and 3n+1 differ only by a factor of 3 each way — and a constant factor of 3 is invisible to Θ. So Θ of any one of them is Θ of all of them. All three are true.

Answer: (a), (b) and (c) are all correct — they name the same growth class up to a constant.

(a) A = n¹⁰⁰, B = 2ⁿ. A polynomial is strictly slower than an exponential, so A = O(B) and A = o(B).

(b) A = (lg n)¹², B = √n. Any power of a logarithm is strictly slower than any power of n, so A = O(B) and A = o(B).

(c) A = √n, B = ncos(πn/8). The exponent cos(πn/8) oscillates forever between −1 and +1, so B keeps swinging from 1/n up to n and back. Sometimes B is far above A, sometimes far below — no single relationship holds for all large n. None of O, o, Ω, ω, Θ apply (a genuine "can't compare" case).

(d) A = 10ⁿ, B = 100ⁿ. Different bases with 100 > 10: the ratio (10/100)ⁿ = 0.1ⁿ → 0, so A is strictly slower: A = O(B) and A = o(B).

(e) A = nlg n, B = (lg n)ⁿ. Compare their logs: lg A = (lg n)², while lg B = n · lg lg n. The second grows far faster (it has a factor of n), so B outgrows A: A = O(B) and A = o(B).

(f) A = lg(n!), B = n lg n. From Problem 2-25, lg(n!) = Θ(n lg n) — same rate. So A = Θ(B) (and therefore also A = O(B) and A = Ω(B), but not the strict little versions).

Answer: (a) O, o · (b) O, o · (c) none · (d) O, o · (e) O, o · (f) Θ (with O and Ω).

First simplify the two that hide a sum:

• f3 is a geometric sum: 1 + 2 + 4 + … + 2ⁿ = 2ⁿ⁺¹ − 1, which grows like 2ⁿ (exponential).
• f4 is the log of that, and log₂(2ⁿ⁺¹) = n + 1, which grows like n (linear).

Now compare the four simplified shapes: n, n(log n)², n² log n, 2ⁿ. To compare f2 = n(log n)² with f1 = n² log n, divide both by n log n: you get log n versus n — and log n is far smaller, so f2 < f1.

Answer: f4 (≈ n)  <  f2 (n log² n)  <  f1 (n² log n)  <  f3 (2ⁿ).

Simplify each:

• f1: adding up √i for i = 1..n is like the area under √x, which grows like n^3/2 (about ⅔·n3/2).
• f4 = 12 n3/2 + 4n — keep the top term: also n^3/2. So f1 and f4 are the same order.
• f2 = (√n)log n = n(log₂ n)/2 — the exponent itself grows with n, so this beats every fixed power of n.
• f3 = n√(log n) — the exponent √(log n) also grows, so this too beats every fixed power — but more slowly than f2, because (log n)/2 eventually dwarfs √(log n).

Answer: f1 = f4 (both n3/2)  <  f3 (n√log n)  <  f2 (n(log n)/2). The key idea: a fixed power like n3/2 is always beaten by n raised to a power that itself keeps growing.