Skiena Chapter 2 —
Every Problem, Explained Simply

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

Count it exactly. The innermost loop k = 1 .. j runs j times, so it adds j to r. So really r is: for every allowed pair (i, j), add j.

Turn it around and count by j instead. For a fixed j (which ranges from 2 to n), how many i's reach it? The rule is i < j, so i can be 1, 2, …, j−1 — that is j−1 values. Each of those contributes j. So the total is

r = 2·1 + 3·2 + 4·3 + … + n·(n−1) = ∑_j=2ⁿ j(j−1)

Adding those up gives a tidy closed form:

r = (n³ − n) / 3

Check on a tiny case. For n = 5: (125 − 5)/3 = 120/3 = 40, which is exactly what the function returns. For n = 10: (1000 − 10)/3 = 330. Both match.

The biggest piece of that formula is n³/3, so the running time is O(n³). (Doubling n multiplies the work by about 8 — the fingerprint of three nested loops that each grow with n.)

Here it is in Python:

def pesky(n):
    r = 0
    for i in range(1, n + 1):              # i = 1 ... n
        for j in range(1, i + 1):          # j = 1 ... i
            for k in range(j, i + j + 1):  # k = j ... i+j
                r += 1
    return r

The scary-looking part is the inner loop: k goes from j up to i + j. So how many numbers is that? Count them: from j to i + j the count is (i + j) - j + 1. The two js cancel out, leaving just i + 1.

So here is the nice surprise: the inner loop always runs i + 1 times, no matter what j is. The wobbly start and stop were a distraction. The length never depended on j at all.

Now it is just three loops that all grow with n, so again the work piles up like n times n times n. That is cubic.

Let us check with tiny numbers. The tidy formula for this one turns out to be n(n+1)(n+2)/3. For n = 5 that is 5 x 6 x 7 / 3 = 70. And if you run pesky(5), you get exactly 70. For n = 10 both give 440. For n = 20 both give 3080. So the counting and the formula agree perfectly.

You do not need to memorise that formula. Just notice it multiplies three things that each grow like n (roughly n times n times n, divided by 3). The divide-by-3 is a fixed shrink that does not change the shape, so the shape is still cubic.

So the running time is O(n³), which means ten times the input is about a thousand times the work.

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

Peel it from the inside out. The innermost loop l = 1 .. (i+j-k) runs i+j-k times. Now sum that over k = j .. i+j. As k climbs, i+j-k counts down: i, i-1, …, 1, 0. Adding 0 + 1 + … + i gives i(i+1)/2.

Next, the j = 1 .. i loop repeats that i(i+1)/2 a total of i times (it does not depend on j), giving i²(i+1)/2. Finally sum over i = 1 .. n:

r = ½ ∑_i=1ⁿ (i³ + i²) = n(n+1)(n+2)(3n+1) / 24

Check: for n = 1 the formula gives 1·2·3·4/24 = 1, and the function indeed returns 1. For n = 2 it gives 2·3·4·7/24 = 7, which also matches.

The biggest piece is proportional to n⁴, so the running time is O(n⁴). (We did not just say "four loops, so n⁴" — that shortcut is not a proof, because loop bounds can change the answer. We actually summed the loops.)

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

Count the innermost loop. k runs from i+j-1 to n, so it repeats n - (i+j-1) + 1 = n - i - j + 2 times — but only when that number is positive (otherwise the loop does nothing). So only pairs with i + j ≤ n + 1 contribute anything.

Doing the inner sum over j first, then over i, the surviving pairs give a clean count. Grouping by i:

r = ∑_i=1^⌊n/2⌋ (n − 2i + 1)(n − 2i + 2) / 2

which works out to (writing m = ⌊n/2⌋):

r = m(m+1)(4m−1)/6  (n even),   m(m+1)(4m+5)/6  (n odd)

Check: both forms agree with the brute-force count for every n up to 40. Only i up to about n/2 contributes (beyond that the inner range is empty), which is why the constant is smaller than for a "full" triple loop.

The biggest piece grows like n³, so the running time is Θ(n³). Doubling n multiplies the work by about 8.

Here is the obvious method. It builds each power of x as it goes:

def evaluate_naive(a, x):
    # a is the list of numbers in front: a[0], a[1], ..., a[n]
    n = len(a) - 1
    p = a[0]
    xpower = 1
    for i in range(1, n + 1):
        xpower = x * xpower       # one multiplication
        p = p + a[i] * xpower     # one multiplication, one addition
    return p

(a) Worst case. Just count the arithmetic inside the loop. The line xpower = x * xpower is one multiply. The line p = p + a[i] * xpower is one multiply (a[i] * xpower) and one add. So every trip around the loop costs two multiplies and one add. The loop runs n times. So the totals are 2n multiplications and n additions.

(b) Average case. Here is the quiet insight. Look at the loop: there is no if, no break, nothing that changes based on the actual numbers. The loop always runs the same n times and always does the same work each time. When the work never depends on the data, the average case cannot be any different from the worst case. So the average is also 2n multiplications.

(c) Can we do better? Yes. The waste is that first multiply, the one that keeps rebuilding xpower from scratch. There is a smarter method called Horner's rule. Instead of building powers, it starts from the top number and folds one number in at a time:

def evaluate_horner(a, x):
    n = len(a) - 1
    p = a[n]                       # start from the top number
    for i in range(n - 1, -1, -1): # i = n-1, n-2, ..., 0
        p = p * x + a[i]           # one multiplication, one addition
    return p

Now the loop body is a single p * x + a[i]: one multiply and one add per trip, over n trips. That is n multiplications and n additions. The additions are the same as before, but the multiplications have been cut in half, from 2n down to n.

Let us see both give the same answer on a tiny example. Take the numbers [2, -3, 1, 4] (which means the polynomial 2 - 3x + x² + 4x³, so n = 3) and plug in x = 2. Both methods return 32. But the obvious method used 6 multiplies (that is 2n = 2 x 3), while Horner used only 3 (that is n = 3). Same answer, half the multiplying.

The code:

m = A[0]                       # current champion
for i in range(1, len(A)):
    if A[i] > m:
        m = A[i]               # a bigger value takes the title
print(m)                       # claim: this is the biggest

Think of it as a sports tournament. m is the current champion — the biggest value we have seen so far. We start by crowning the first item as champion. Then each new item steps up as a challenger. If the challenger is bigger, it becomes the new champion. If not, the old champion keeps the belt.

To prove this always works, we lean on one simple sentence that stays true the whole way through. (A sentence that stays true through every loop trip has a name: a loop invariant.) Ours is:

After we have looked at the first k items, m holds the biggest of those k.

If that sentence is still true at the very end — when we have looked at every item — then m must hold the biggest of the whole list. So all we have to do is show it can never become false. Two little checks do it.

The start. Before the loop we set m = A[0]. With just one item looked at, the biggest of that one item is obviously itself. So the sentence is true at the start.

Each step keeps it true. Suppose the sentence is true after k items, so m is the biggest of the first k. Now the next item, A[k], steps up. Only two things can happen:

• The newcomer is bigger — the if fires, m becomes A[k], and since it beat the old champion (which had already beaten everyone before it), m is now the biggest of all k + 1 items.
• The newcomer is not bigger — we leave m alone. It is still the biggest of the first k, and those were all at least as big as the newcomer, so m is still the biggest of all k + 1.

Either way the sentence survives the step. So it is true after one item, and each trip carries it safely from k items to k + 1 items. Therefore it is still true after the last item — which means the m we print really is the biggest in the whole list.

Trace it once by hand on a tiny list, say [3, 7, 2]: champion starts at 3, then 7 beats it (champion becomes 7), then 2 loses (champion stays 7). Out comes 7, the biggest. That is exactly the running-champion argument, just done with real numbers.

All of Big-O is about one question: as the input gets bigger, how fast does the work grow? Not the exact number of steps — just the growth. Here are the five symbols in plain words. Whenever you see one, read the plain words instead.

Two handy facts that come up again and again:

• Θ = O and Ω together. If something is both a ceiling and a floor, it pins the rate exactly.
• Big-O ignores constant factors and smaller pieces. 5n, n, and 1000n all count as the same: linear. And in n² + n, the little + n does not matter — only the biggest piece, n², counts.

The growth ladder (your everyday tool)

Almost every problem in this chapter is solved by this one picture. It lists common functions from slowest-growing to fastest-growing. The symbol ≪ means “grows slower than”.

1  ≪  log n  ≪  √n  ≪  n  ≪  n log n  ≪  n²  ≪  n³  ≪  2ⁿ  ≪  3ⁿ  ≪  n!

The recipe for almost every true/false or relationship question: replace each side by where it sits on the ladder, then compare. If the left side is lower on the ladder, it is O of the right. If higher, it is Ω. If they land on the same rung, it is Θ.

A few ladder facts worth memorising, because they settle most questions instantly:

• Any power of n (even tiny √n) beats any logarithm.
• Any exponential (like 2ⁿ) beats any polynomial (like n³ or n¹⁰⁰).
• n! beats every fixed-base exponential.
• Bases matter for exponentials: 2ⁿ ≪ 3ⁿ. But adding a constant to n does not matter: 2ⁿ⁺¹ = 2·2ⁿ is the same rate as 2ⁿ.

(a) Rewrite it: 2ⁿ⁺¹ = 2 · 2ⁿ. That is just 2ⁿ with a 2 stuck on the front — a constant factor. Big-O throws away constant factors, so this stays the same rate. At n=10: 2ⁿ⁺¹ = 2048 and 2ⁿ = 1024. Always exactly double, never runs away.

(b) Rewrite it: 2²ⁿ = (2ⁿ)² = 4ⁿ. That is a bigger base, 4 instead of 2. Their ratio is 4ⁿ / 2ⁿ = 2ⁿ, which itself shoots off to infinity. No fixed number c can hold 4ⁿ below c · 2ⁿ. At n=10: 4ⁿ = 1,048,576 versus 2ⁿ = 1024 — already 1024 times bigger, and the gap keeps widening. Doubling the exponent changes the base; it is not a constant factor.

None of these pairs lands on the same rung, so there is no Θ tie here.

Θ(n³) means “trapped between two constant copies of n³ once n is big”. The clean trick: divide the whole thing by n³ and watch it settle.

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

Each little fraction (3/n, 1/n², 1/n³) shrinks to 0 as n grows, so the whole ratio settles near 1. That means the expression is basically n³ for large n — caught between, say, 0.5 n³ and 1 · n³. Quick check at n=10: the value is 1000 − 300 − 10 + 1 = 691, and indeed 500 ≤ 691 ≤ 1000. Two constant copies of n³ trap it — that is the definition of Θ.

This is the headline ladder fact: an exponential eventually overtakes any polynomial and never looks back. To prove it we just need one constant c and a starting point n₀ so that n² ≤ c · 2ⁿ from there on. Watch the race:

At n=3 the polynomial briefly leads (9 > 8), but from n=4 onward 2ⁿ catches up and then pulls away for good. At n=10 it is already ten times bigger, and the gap only grows. So with c = 1 and n₀ = 4 we have n² ≤ 2ⁿ for all n ≥ 4 — exactly what a ceiling needs.

(a) f = n² + n + 1, g = 2n³. For n > 1, both n and 1 are at most n², so f ≤ 3n². And 3n² ≤ 4n³ = 2 · (2n³). So c = 2 works.

(b) f = n√n + n² (that is n¹·⁵ + n²), g = n². For n > 1, n¹·⁵ ≤ n², so f ≤ n² + n² = 2n². So c = 2.

(c) f = n² − n + 1, g = n²/2. Since −n + 1 ≤ 0 for n ≥ 1, we get f ≤ n² = 2 · (n²/2). So c = 2.

Many other constants would also work — you only need to show one.

Remember what a ceiling means: f = O(g) is just “f ≤ c · g for big n”. So we start with two facts:

f₁ ≤ c₁ · g₁   and   f₂ ≤ c₂ · g₂

Add them straight down: f₁ + f₂ ≤ c₁ g₁ + c₂ g₂. Now let c be the bigger of c₁ and c₂. Then the right side is at most c(g₁ + g₂). Done — the sum has ceiling g₁ + g₂.

It is the exact same argument as 2-13 and 2-15, just with the inequalities flipped. A floor means f ≥ c · g for big n. So:

• Sum: add f₁ ≥ c₁ g₁ and f₂ ≥ c₂ g₂; take the smaller of the two c's, and you get a floor on the sum.
• Product: multiply the two (everything positive) to get a floor on the product, with constant c₁ c₂.

And since Θ is just a ceiling and a floor together, both rules automatically hold for Θ too.

Start with the same two facts (all quantities positive):

f₁ ≤ c₁ · g₁   and   f₂ ≤ c₂ · g₂

Multiply them together: f₁ · f₂ ≤ (c₁ c₂) · g₁ · g₂. The single constant c₁ c₂ does the whole job, so the product has ceiling g₁ · g₂.

This is the formal version of “keep the highest power”. Take any single term ai ni where i ≤ k. Once n ≥ 1, a lower power of n is no bigger than the top power nk, so |ai ni| ≤ |ai| · nk. Add up all k+1 terms:

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

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

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

(n + a)ᵇ / nᵇ = (1 + a/n)ᵇ → 1  as n grows

Because a/n shrinks to 0, the ratio settles at 1. So for big n the expression stays trapped between two fixed constants (say ½ nᵇ and 2 nᵇ) — the sandwich that means Θ.

n   2ⁿ   n lg n   ln n   n − n³ + 7n⁵   lg n   √n   eⁿ   n² + lg n   n²   2ⁿ⁻¹   lg lg n   n³   (lg n)²   n!   n^1+ε (0<ε<1)

First, tidy each one into its shape:

• n − n3 + 7n5 → keep the top term, n5.
• n2 + lg n → n2 (the lg n is a speck next to n2) — so it ties with plain n2.
• ln n and lg n differ only by a constant factor → they tie (both Θ(log n)).
• 2n−1 = ½·2n → ties with 2n.
• en is above 2n, because e > 2 (so en/2n = (e/2)n → ∞).
• n1+ε with 0<ε<1 sits between n lg n and n2 (a real power above n, but below n2).

Now walk up the ladder. The only surprise to watch: any real power of n (even √n) beats every power of a logarithm.

√n   n   2ⁿ   n log n   n − n³ + 7n⁵   n² + log n   n²   n³   log n   n^1/3 + log n   (log n)²   n!   ln n   n/log n   log log n   (1/3)ⁿ   (3/2)ⁿ   6

Tidy the tricky ones first:

• (1/3)n → a fraction to a growing power shrinks toward 0. It is the smallest of all.
• 6 → a constant, Θ(1); above anything that goes to 0, below anything that grows.
• n − n3 + 7n5 → n5;  n2 + log n → n2 (ties with n2);  n1/3 + log n → n1/3.
• log n and ln n tie (Θ(log n)). n/log n is just below n (a shade under linear, but far above √n).
• (3/2)n is below 2n (smaller base), and both beat every polynomial.

The one easy-to-slip pair: (log n)2 versus n1/3. Squaring a logarithm still leaves a logarithm, and any real power of n (even the small power 1/3) eventually beats any power of log n. So (log n)2 < n1/3 — even though for small n the log looks bigger.

(a) Want f = o(g) (strictly slower) and f ≠ Θ(g) (not the same rate). Easy. Take f = n, g = n². n is strictly slower than n², and they are clearly not the same rate. In fact “strictly slower” always rules out “same rate”, so any little-o pair works.

(b) Want f = Θ(g) and f = o(g) at once. Impossible. Θ says “exactly the same rate”; little-o says “strictly slower”. Nothing can be both exactly as fast and strictly slower.

(c) Want f = Θ(g) but f ≠ O(g). Impossible. Θ is a ceiling and a floor together, so f = Θ(g) already includes f = O(g). You cannot keep the first and drop the second.

(d) Want f = Ω(g) (floor) but f ≠ O(g) (no ceiling). Easy. Take f = n², g = n. n² grows at least as fast as n (floor holds), but it is not capped by n (no ceiling). That is the picture of a strict lower bound.

(a) f = n² + 3n + 4, g = 6n + 7. f is quadratic, g is linear, so f grows faster: f = Ω(g) (and definitely not a ceiling).

(b) f = n√n = n¹·⁵, g = n² − n. g is basically n², above n¹·⁵, so f is the smaller one: f = O(g).

(c) f = 2ⁿ − n², g = n⁴ + n². The 2ⁿ completely swamps the −n² (a rounding error beside it), so f grows like 2ⁿ — an exponential, above the polynomial g: f = Ω(g).

(a) Worst case O(n²) — can it be O(n) on some inputs? Yes. Some inputs (like a best case) can finish far faster; the ceiling only caps the slowest.

(b) Worst case O(n²) — can it be O(n) on all inputs? Yes. O(n²) is only an upper bound; an algorithm that is actually linear everywhere is still (loosely) O(n²). O does not claim the bound is tight.

(c) Worst case Θ(n²) — can it be O(n) on some inputs? Yes. Θ pins the worst case at quadratic, but the best case (some inputs) can still be linear.

(d) Worst case Θ(n²) — can it be O(n) on all inputs? No. A Θ(n²) worst case means some inputs genuinely force quadratic work, so not every input can be linear.

(e) Is f(n) = Θ(n²) when f = 100n² for even n and f = 20n² − n·log²n for odd n? Yes. Either way, every value sits between constant copies of n² (roughly between 19n² and 100n² for large n), so the whole function is Θ(n²) no matter which branch it takes.

(a) Is 3ⁿ = O(2ⁿ)? No. The ratio 3ⁿ / 2ⁿ = (3/2)ⁿ = 1.5ⁿ races off to infinity, so no constant can cap it. Different bases are not a constant factor apart.

(b) Is log(3ⁿ) = O(log(2ⁿ))? Yes. Take logs: log(3ⁿ) = n log 3 and log(2ⁿ) = n log 2. Their ratio is the fixed number log 3 / log 2 ≈ 1.585 — a constant factor — so each is a ceiling of the other. Taking the log tamed the exponential into a linear function of n.

(c) Is 3ⁿ = Ω(2ⁿ)? Yes. A floor asks whether 3ⁿ grows at least as fast as 2ⁿ — and it grows much faster, so certainly at least as fast.

(d) Is log(3ⁿ) = Ω(log(2ⁿ))? Yes. Same constant-ratio picture as (b): n log 3 versus n log 2. A constant factor apart means each is both a ceiling and a floor of the other.

A Σ (sigma) just means "add these up".

(a) Add up 1/i: that is 1/1 + 1/2 + 1/3 + ... + 1/n. Each new piece is tiny, so the total creeps up very slowly. It turns out to stay close to log n forever (the gap between them settles near 0.577 and stops moving). So the total grows at the same rate as log n.

(b) Add up ⌈1/i⌉: the ⌈ ⌉ brackets mean "round up to the next whole number". For any i of 1 or more, 1/i is a number between 0 and 1, so rounding it up always gives exactly 1. Adding 1 to itself n times gives n. So the total grows like n.

(c) Add up log i: that is log 1 + log 2 + ... + log n. A handy fact: adding logs is the same as taking the log of the product. So this equals log(1 · 2 · 3 · ... · n) = log(n!). See part (d): it grows like n log n.

(d) log(n!): here n! means 1 · 2 · ... · n. At least half of those factors are n/2 or bigger, so n! is at least (n/2) multiplied by itself n/2 times — that makes log(n!) at least about (n/2)·log(n/2), which is on the order of n log n. And n! is at most n multiplied by itself n times, so log(n!) is at most n log n. Squeezed from both sides, it grows like n log n.

The four are:

• f1 = n² log n
• f2 = n (log n)²
• f3 = 2⁰ + 2¹ + ... + 2ⁿ (add up the powers of two)
• f4 = log of that same sum

First, tidy up the two that hide a sum. A sum of powers that keep doubling is basically its last term. So f3 = 1 + 2 + 4 + ... + 2ⁿ adds up to just over 2ⁿ — it grows like 2ⁿ. And f4 is the log of that. Since the log of 2ⁿ is about n, f4 grows like n.

Now compare the simple shapes: n, n(log n)², n² log n, 2ⁿ. To see which of f2 and f1 is bigger, divide both by n log n: f2 becomes log n, f1 becomes n. Since n is far bigger than log n, f1 beats f2.

The four are:

• f1 = √1 + √2 + ... + √n (add up the square roots)
• f2 = (√n)^{log n}
• f3 = n^{√(log n)}
• f4 = 12·n^1.5 + 4n

Simplify each:

f1: adding up √1, √2, ..., √n grows like n1.5 (about two-thirds of n^1.5).

f4: keep the biggest piece, 12·n^1.5, and drop the constant — it is also n1.5. So f1 and f4 grow at the same rate (a tie).

f2: this rewrites as n raised to the power (log n)/2. The power itself grows with n, so it beats any fixed power of n.

f3: this is n raised to the power √(log n). That power grows too, so it also beats any fixed power — but slower than f2, because (log n)/2 eventually gets much bigger than √(log n).

Two easy facts do all the work:

• If you add up n terms whose biggest is a power like i^k, the total grows like n^k+1 (roughly n copies of the top term).
• A sum where each term is a fixed multiple of the last (like 4ⁱ, which keeps quadrupling) is basically its final term.

(a) add up 3i⁴ + 2i³ − 19i + 20: the biggest piece is i⁴, and adding up i⁴ grows like n⁵. So Θ(n⁵).

(b) add up 3·4ⁱ + 2·3ⁱ − i¹⁹ + 20: the 4ⁱ term quadruples each step and outgrows everything. That sum is basically its last term, 4ⁿ. So Θ(4ⁿ).

(c) add up 5i + 3·2ⁱ: the 2ⁱ term doubles each step and beats the plain 5i. The sum is basically its last term. So Θ(2ⁿ).

The three guesses are: (a) S grows like 3ⁿ⁻¹, (b) S grows like 3ⁿ, (c) S grows like 3ⁿ⁺¹.

A sum of powers that keep tripling is basically its last term. Working it out exactly, S = (3ⁿ⁺¹ − 3) / 2, which is about 3ⁿ⁺¹/2. Either way, the last term rules, so S grows like 3ⁿ.

Here is the trick: 3ⁿ⁻¹, 3ⁿ, and 3ⁿ⁺¹ only differ by a factor of 3 up or down. And a plain factor of 3 does not change a growth rate — Θ ignores constant multipliers. So all three name the very same growth class.

(a) f = 1000·2ⁿ + 4ⁿ: note 4ⁿ equals (2ⁿ)², so it dwarfs 2ⁿ no matter how big the 1000 is. Keep 4ⁿ. So Θ(4ⁿ).

(b) f = n + n log n + √n: of the three, n log n grows fastest. So Θ(n log n).

(c) f = log(n²⁰) + (log n)¹⁰: the first piece is just 20 log n (a constant times log n). The second is a much higher power of log n and wins. So Θ((log n)¹⁰).

(d) f = (0.99)ⁿ + n¹⁰⁰: a base below 1 means (0.99)ⁿ shrinks toward 0 as n grows, so it adds nothing. Only n¹⁰⁰ matters. So Θ(n¹⁰⁰).

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

(b) A = (log n)¹², B = √n: any power of a log is strictly slower than any power of n. So O and o.

(c) A = √n, B = n^cos(πn/8): the cos part swings forever between −1 and +1, so B keeps swinging from 1/n up to n and back. Sometimes B is way above A, sometimes way below — no single relationship holds for all big n. So none apply (a genuine "can't compare" case).

(d) A = 10ⁿ, B = 100ⁿ: since 100 > 10, the ratio 0.1ⁿ shrinks to 0, so A is strictly slower. So O and o.

(e) A = n^{log n}, B = (log n)ⁿ: compare their logs: log A = (log n)², while log B = n · log log n. The second grows far faster (it has a factor of n), so B beats A. So O and o.

(f) A = log(n!), B = n log n: from Problem 2-25, log(n!) grows at the same rate as n log n. So Θ (and therefore also O and Ω, but not the strict little versions).

We add the squares 1, 4, 9, 16, ... but flip the sign on every second one: plus, minus, plus, minus. The claim is that the messy total is always just k(k+1)/2 (the plain "add 1 up to k" number), with a plus sign when k is odd and a minus sign when k is even. (That is all the (−1)^k−1 factor does: +1 for odd k, −1 for even k.)

Check small cases and watch both sides line up:

Why it works: pair each minus with the plus just before it: (1² − 2²), (3² − 4²), and so on. Each such pair equals the negative of the two numbers added together. So the whole plus-minus sum of squares turns into a plain running total of 1, 2, 3, ... (carrying a sign) — and a running total of 1 up to k is exactly k(k+1)/2. The final sign is whatever the last term had: plus for odd k, minus for even k.

The triangle starts like this:

Add up each row: row 1 gives 1, row 2 gives 3, row 3 gives 9, row 4 gives 27. That is 1, 3, 9, 27 — the powers of three. So the answer looks like 3i−1.

Why: ask where each entry lands in the row below. Every entry is one of the "three above" for exactly three spots underneath it — the slot below-left, the slot directly below, and the slot below-right. So each entry passes its full value down three times. Add that across the whole row: (sum of next row) = 3 × (sum of this row). The total triples at every step. Row 1 starts at 1, so row i is 1 tripled i−1 times, which is 3ⁱ⁻¹.

One day at a time: on day d the true love brings 1 + 2 + ... + d presents (that day's new gift plus everything repeated). That is the "add 1 up to d" number, so day d brings d(d+1)/2 presents.

Add up all the days: the grand total is the sum of each day's haul, Σ (for d = 1 to n) of d(d+1)/2. A small table:

Those running totals 1, 4, 10, 20 have a tidy formula: n(n+1)(n+2)/6. Check it: for n = 4 that is 4·5·6/6 = 20. For the real song, n = 12: 12·13·14/6 = 2184/6 = 364.

One pass of the outer loop: fix i. The inner loop runs j from i up to and including 2i. How many whole numbers is that? (2i − i) + 1 = i + 1. (The "+1" is because both ends count.) Quick check with i = 3: j is 3, 4, 5, 6 — four values, and i + 1 = 4. Good.

(a) Add up every outer pass: the outer loop does this for i = 1, 2, ..., n, so add up (i + 1) for each. As a sum: T(n) = Σ_i=1ⁿ (i + 1) (that Σ just means "add these up").

(b) Simplify: split into two easier sums:

T(n) = (1 + 2 + ... + n) + (1 + 1 + ... + 1). The first bracket is the "add 1 up to n" number, n(n+1)/2. The second is 1 added n times, which is n. So T(n) = n(n+1)/2 + n = (n² + 3n)/2.

The biggest piece is n², so this grows like Θ(n²) — the usual two-nested-loops behaviour.

The loops run: i from 1 to n/2, then j from i to n−i, then k from 1 to j, printing once at the centre.

(a) The nested-sum form (each loop becomes one ∑, the printed line is the "1" being counted):

T(n) = ∑_i=1^n/2 ∑_j=iⁿ⁻ⁱ ∑_k=1^j 1

(b) Simplify. The innermost ∑k=1j 1 is just j. So

T(n) = ∑_i=1^n/2 ∑_j=iⁿ⁻ⁱ j

The inner sum adds the whole numbers from i up to n−i, which is [(n−i)(n−i+1) − (i−1)i] / 2. Now write n = 2m and show the work:

T(n) = ∑ [ (2m-i)(2m-i+1) - (i-1)i ] / 2   (i = 1..m, n = 2m)
     = ∑ m(2m - 2i + 1)
       # numerator simplifies to 2m(2m - 2i + 1)
     = m [ (2m-1) + (2m-3) + ... + 1 ]
       # these are the odd numbers 1 .. 2m-1
     = m · m2 = m3 = (n/2)3 = n3/8
       # the first m odd numbers sum to m2

Check: for n = 4 (m = 2) this predicts 8, and counting the prints by hand gives 8. For n = 10 it predicts 125, which also matches a direct count.

To do x × y by repeated addition, we add x to a running total y times. So the cost depends on how big y can get. An n-digit number in base b is at most about bⁿ (in base 10 a 3-digit number reaches about 10³ = 1000; in base 2 a 3-bit number reaches about 2³ = 8). So y can force about bⁿ additions.

Each addition is of two n-digit numbers, which costs about n steps (add digit by digit, carrying). Multiply the two together: about bⁿ additions × about n per addition gives O(n · bn).

That bⁿ is exponential in n — runaway growth. Fine for 5 × 4, hopeless for real numbers.

Long multiplication pairs every digit of one number with every digit of the other. With n digits each, that is n × n = n² single-digit multiplications. Then we line up those partial rows and add them — that is another n²-ish of work (about n rows, each up to about n digits wide).

So: n² single-digit products + about n² additions to combine gives O(n²).

Stand the two methods side by side:

Keep flipping between the two ways of saying the same thing: "log_a x = p" and "x = a^p". That single trick unlocks all four rules.

(a) log(x·y) = log x + log y. Say x = a^p and y = a^q. When you multiply two powers you add the exponents: x·y = a^p+q. So the exponent for x·y is p + q, which is log x + log y. (This is the old trick that turned multiplication into addition on slide rules.)

(b) log(x^y) = y · log x. With x = a^p, raising to the power y multiplies the exponent: x^y = a^p·y. So the exponent is p·y, which is y · log x.

(c) change of base: log_a x = log_b x / log_b a. Start from x = a^p where p = log_a x. Take log base b of both sides and use rule (b): log_b x = p · log_b a. Divide across and p = log_b x / log_b a.

(d) x^{log_b y} = y^{log_b x}. Two things are equal if their logs match. Take log base b of each side using rule (b): the left gives log_b y · log_b x, the right gives log_b x · log_b y. Same product, so the two sides are equal.

Rule (c) is the important one for this course. It says any two bases differ only by a fixed number (1 / log_b a). Big-O throws away fixed multipliers, so the base of a log never matters for Big-O. That is why we happily write O(log n) without ever saying which base.

Both sides are secretly counting the same thing: how many bits n needs to be written in binary, which is the same as how many times you halve n before you reach 1. Let us just make a small table and watch the two columns agree.

The third column and the last column match on every row. Nice and simple.

The biggest number you can write with b bits is all ones: 1 bit reaches 1, 2 bits reach 3, 3 bits reach 7, 8 bits reach 255. So a number n needs exactly b bits when it fits in b bits but not in b−1. In symbols, n sits between 2^b−1 and 2^b (that is, 2^b−1 ≤ n < 2^b). Taking lg of that, b−1 ≤ lg n < b, so rounding lg n down gives b−1, and b = ⌊lg n⌋ + 1. A tiny table shows it:

No cheating, just a disguise. Simplify the log with rule (b) from problem 2-39. Since √n = n^1/2:

log √n = log(n^1/2) = ½ · log n

So O(n log √n) = O(n · ½ log n) = O(½ · n log n). The ½ is just a fixed multiplier, and Big-O throws fixed multipliers away. So this is O(n log n) — the very same class.

This is called reservoir sampling. Start with the easiest version, keeping just k = 1.

The rule: when the i-th number arrives (counting 1, 2, 3, …), keep it with probability 1/i; otherwise stick with the one you already hold. So you always keep the 1st. You swap to the 2nd with chance 1/2. You swap to the 3rd with chance 1/3. And so on.

Why is that fair? The very last number, number n, is kept with chance 1/n straight away — good. An earlier number j was kept when it arrived (chance 1/j) and then had to survive every later number choosing not to replace it. Those survival chances multiply out to j/n. Put together, everyone ends up with the same 1/n. Fair.

For a handful of k: keep the first k as your starting "reservoir". When the i-th number arrives (with i bigger than k), keep it with chance k/i; if you keep it, randomly throw out one of the k you were holding to make room. The same argument gives every number the final chance k/n.

import random

def reservoir(stream, k):
    keep = []
    for i, item in enumerate(stream):   # i counts from 0; n never needed
        if i < k:
            keep.append(item)           # fill the reservoir first
        else:
            j = random.randint(0, i)    # keep with probability k/(i+1)
            if j < k:
                keep[j] = item
                # evict a random held item and insert the new one
    return keep

It reads the stream once, stores only k items, and never needs to know the total ahead of time — perfect for a stream too big to hold or of unknown length.

The core idea is simple: keep three copies of every item, on three distinct nodes, and never let two items live on the exact same trio of nodes. An easy way: put item i on nodes i, i+1 and i+2 (wrapping around at the end). Now every item has three homes, every node still holds three items, and each item's trio of homes is different.

An item is only lost if all three of its nodes die. If 3 random nodes fail, one item is lost only if those 3 dead nodes are exactly its 3 homes. The chance of that for one item is 1 divided by the number of ways to pick 3 nodes out of 1000 — a huge number, about 166 million. So one item's chance of loss is tiny. Add it up over all 1000 items:

E[items lost] = 1000 / C(1000, 3) ≈ 6.02 × 10⁻⁶

Read that carefully: it is not "6 lost per million items". It means the expected number of items lost per 3-node failure is about 6 × 10⁻⁶ — equivalently, only about a 6-in-a-million chance that a given random 3-node failure destroys even one item. Almost always you lose nothing.

Careful about what is counted. Setting up tmp = A[0] at the start is the initial value, not one of the assignments we are counting. We only count the assignments made during the scan, at positions i = 1 .. n.

When does position i assign? Only when A[i] is smaller than everything seen before it — i.e. when A[i] is the smallest among the first i+1 numbers A[0..i]. In a random order, each of those i+1 numbers is equally likely to be the smallest, so the chance is 1/(i+1).

Add the chances over the scanned positions i = 1 .. n:

expected assignments = ∑_i=1ⁿ 1/(i+1) = 1/2 + 1/3 + … + 1/(n+1) = H_n+1 − 1

Here Hm = 1 + 1/2 + … + 1/m is the harmonic number, and Hn+1 − 1 is just it with the first term (the 1) removed. It grows about like ln n — painfully slowly:

(A quick simulation over many random shuffles agrees: about 2.0 for n = 10 and about 3.5 for n = 50.) If your array is defined as exactly n elements instead, the same argument gives Hn − 1.

(a) Lots of marbles → binary search. A broken marble costs you nothing, so you can gamble on the middle floor every time. Drop from 50. If it breaks, the answer is below 50; if not, above. Each drop halves the range, so you need ⌈lg 100⌉ = 7 drops — the same halving trick as binary search.

(b) Only two marbles → you cannot halve. If your first marble breaks at floor 50, you only have one marble left, and you dare not gamble with it — you must walk up one floor at a time from the last safe floor. So a big first jump risks up to 49 more drops. The fix: make the first marble take shrinking steps, so that whichever gap it breaks in, the walk-up with the second marble is short.

Drop the first marble at floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 — gaps of 14, then 13, then 12, shrinking by one each time.

Why start at 14? If the first marble breaks on drop number d, you have already spent d drops and the gap left to walk is 14 − d floors — always about 14 total. You want the first step k big enough that k + (k−1) + … + 1 = k(k+1)/2 covers all 100 floors. The smallest k that works is 14, because 14 × 15 / 2 = 105 ≥ 100, while 13 × 14 / 2 = 91 falls short.

The trick is to make each bag leave a different, recognisable fingerprint on one pile. Number the bags 1 to 10. Take 1 coin from bag 1, 2 coins from bag 2, 3 from bag 3, …, 10 from bag 10 — that is 55 coins in all.

If every coin were real, the pile would weigh 55 × 10 = 550 grams. Each fake coin is 1 gram light, and bag k put in exactly k coins. So if bag k is the fake one, the pile reads 550 − k grams. The number of grams missing is the guilty bag's number.

weights = [10] * 10       # ten bags, all 10-gram coins to start
weights[6] = 9            # bag number 7 secretly holds 9-gram coins

# take (i+1) coins from bag i and weigh them all together
total = sum((i + 1) * weights[i] for i in range(10))
print(550 - total)        # 7  -> the light bag is number 7

Weigh 5 grams missing? Bag 5. Weigh 7 missing? Bag 7. One weighing tells you everything.

A balance scale gives three possible answers each time: left heavier, right heavier, or level. So two weighings can tell apart up to 3 × 3 = 9 things, and 9 ≥ 8. That count tells you it must be possible. Here is how. Split the 8 balls into groups of 3, 3 and 2.

1. Weighing 1: put the two groups of 3 on the pans.
   • If they balance, the heavy ball is one of the 2 set aside. Weigh those two against each other — the heavier pan shows it. Done in two.
   • If one side is heavier, the heavy ball is among those 3.
2. Weighing 2 (heavy ball is in a group of 3): take that group and weigh 1 ball against another 1. If one is heavier, that is it; if they balance, it is the third ball you left off.

The easy half first: each merge turns two companies into one, so it shrinks the count by exactly one. Going from n down to 1 always takes n − 1 merges, whatever the order.

The harder half is: how many different orders can the merges play out in? Do the small cases by hand:

The formula that produces 1, 3, 18, … is:

number of merge orders = n! · (n−1)! / 2ⁿ⁻¹

Check it: n = 2 gives 2 · 1 / 2 = 1; n = 3 gives 6 · 2 / 4 = 3; n = 4 gives 24 · 6 / 8 = 18. All match.

The lazy way is four nested loops over a, b, c, d — that is O(n⁴), hopeless. The trick is the same "remember what you have seen" idea from the fast anagram and two-sum solutions: build every two-cube sum once and look for collisions.

Go over every pair (a, b) with a ≤ b < n (about n²/2 of them), compute a³ + b³, and drop it into a dictionary whose key is that sum. Any key that ends up with two or more different pairs is a Ramanujan number.

def ramanujan(n):
    seen = {}                     # sum -> list of (a, b) pairs
    for a in range(1, n):
        for b in range(a, n):     # a <= b avoids counting a pair twice
            seen.setdefault(a**3 + b**3, []).append((a, b))
    return {s: p for s, p in seen.items() if len(p) >= 2}

print(sorted(ramanujan(20)))

The smallest is the famous 1729 = 1³ + 12³ = 9³ + 10³ — the "taxicab number" from the Hardy–Ramanujan story. Building the dictionary is one pass over the ≈ n²/2 pairs, each insert O(1) on average, so the whole thing is O(n²) time and O(n²) space.

The trick for every puzzle like this is to reason backwards from the smallest case, because when a pirate votes he compares "what I get now" against "what I would get if this proposer is thrown overboard". Call the pirates P1 (most junior) up to P6 (most senior); the senior proposes first. "At least half" means a tie is enough to pass.

Part 2-51, splitting $300. Build it up one pirate at a time:

Each proposer only bribes the cheapest pirates — the ones who would get nothing in the next round — and only just enough of them to reach half the votes. So with 6 pirates, the senior P6 needs 3 votes (his own plus two), and he gets them by handing $1 each to P4 and P2, keeping $298.

Part 2-52, a single indivisible dollar. Now the proposer has almost nothing to bribe with, so survival votes do the work. Reason down the chain: with 5 pirates the proposer P5 would need 3 votes but can only bribe one pirate with the single dollar — so a 5-pirate proposal fails and P5 would be thrown overboard. That fact is the key: P5 is desperate to never reach a 5-pirate game.

So when 6 pirates face the single dollar, the senior P6 needs 3 votes and gets them like this: his own vote; P5's vote for free (because if P6 goes overboard the game drops to 5 pirates where P5 dies, so P5 backs almost anything that keeps P6 afloat); and one more vote bought by giving the single dollar to one pirate who would otherwise get nothing (P4, P3, or P1). That is three votes — it passes.

Primary Arithmetic — count the carries when you add two numbers. Add them the grade-school way, digit by digit from the right, keeping a running carry. Every column where the two digits plus the incoming carry reach 10 makes a carry into the next column. Count those events. It is O(number of digits) — really just "do primary-school addition and watch the carries", then report none, one, or the count.

A Multiplication Game — two players start from a product of 1 and take turns multiplying it by any number from 2 to 9; the first to reach or pass n wins, and Stan goes first. Solve it by reasoning backwards. With best play the winner depends only on which "band" n falls in, and the band edges are 9, 18, 162, 324, 2916, … — the gaps alternate ×2 then ×9 (not "powers of nine"): Stan wins for n in 2–9, the second player for 10–18, Stan for 19–162, the second player for 163–324, Stan for 325–2916, and so on. A clean way to decide: repeatedly replace n by ceil(n / 18) until n ≤ 18; then Stan (first) wins exactly when the leftover n ≤ 9. No search needed — a handful of divisions.

Light, More Light — lamps 1..N start off; person i flips every lamp whose number is a multiple of i, so lamp k is flipped once for each of its divisors. A lamp ends on only if it was flipped an odd number of times, i.e. if k has an odd number of divisors. Divisors normally come in pairs (d and k/d), except when k is a perfect square (the square root pairs with itself). So the only lamps left on are the perfect squares. The whole problem becomes: is k a perfect square? Check with an integer square root, O(1) per query.