Big-O Notation

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.

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 full n-sized loops would give n³ work, but dependent bounds can change the growth rate. Here the sum derived below establishes a cubic leading term. That predicts doubling n will eventually 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³. For every n ≥ 10, 3/n ≤ 0.3 and 1/n² ≤ 0.01, so the ratio is at least 1 − 0.3 − 0.01 = 0.69 ≥ 0.5. Also −3n² − n + 1 ≤ 0 for n ≥ 1, giving the upper bound n³. Thus c₁ = 0.5, c₂ = 1 and n₀ = 10 work for all later n. At n = 10 the value 691 lies between 500 and 1000; this is a check, not the proof.

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 = 4, n² = 2ⁿ = 16. Suppose n² ≤ 2ⁿ for an integer n ≥ 4. Then (n+1)² ≤ 2n² because n² − 2n − 1 ≥ 0, and hence (n+1)² ≤ 2n² ≤ 2 · 2ⁿ = 2ⁿ⁺¹. Induction establishes the inequality for every integer n ≥ 4. Thus c = 1 and n₀ = 4 are valid witnesses; the displayed table is a check on this argument.

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 Ω).