Maths for Algorithms: Logs, Powers, Summations

By the end of this lesson you will be able to compute and reason about powers and logarithms by hand, read and evaluate Σ (sigma) summation notation, derive closed forms for the sums that show up when you count loop operations, compare the growth rates of the functions you'll meet constantly in algorithm analysis (log n, √n, n, n log n, n², n³, 2ⁿ, n!), and follow — and reproduce — a simple proof by mathematical induction. This is the toolbox the rest of the Algorithms track assumes you already own.

1. Powers: doubling and the chessboard

bⁿ ("b to the power n") means multiply b by itself n times: 2³ = 2×2×2 = 8. b is the base, n is the exponent. Watch the grains pile up one square at a time:

In Dart: the same doubling as a loop, and as 1 << n (a left shift is "multiply by 2ⁿ"); the chessboard total needs BigInt because 2⁶³ no longer fits a 64-bit int.

Input size → what's feasible: n ≤ 62 → plain int holds 2ⁿ; n up to 64 (or thousands) → use BigInt; n = 10⁹ → you can only talk about the exponent, never write the number.

Three exponent rules let you combine powers without ever multiplying the whole thing out — and the verify file checks every one of these numerically:

In Dart: each exponent rule as an equality that the program checks on concrete numbers (b⁰ = 1 is the loop that never runs, b⁻ⁿ needs a double because it is a fraction).

Input size → what's feasible: exponents up to ≈ 62 for base 2 (≈ 39 for base 3) before a 64-bit int overflows; for bigger ones use BigInt or modular arithmetic.

2. Logarithms: "how many times can I halve it?"

Formally, log_b(x) = y means "b raised to the power y gives x", i.e. bʸ = x. In computer science the default base is almost always 2 (because computers split things in half or store bits), so we abbreviate lg n = log₂ n.

In Dart: log_b x = y means b^y = x. For base 2 the code is literally "count the halvings"; the guessing game is a binary search over 1…64.

Input size → what's feasible: x ≤ 10¹⁸ → at most 59 halvings; so a loop (or x.bitLength - 1) is O(log x), trivial even for 10⁶ queries.

In Dart: the three log rules and change of base, each typed as lg(...) arithmetic and compared on concrete numbers (the page's 8 · 4 = 32 example, plus all x, y in 1…50). Dart has no built-in log2 for doubles, so lg x = math.log(x) / math.ln2 is the change-of-base formula itself.

Input size → what's feasible: x, y ≤ 10⁹ → all of these are O(1) calls to math.log; the answers are doubles, so compare with a tolerance (here 10⁻⁹), never with ==.

In Dart: the "base is only a constant factor" claim, as code: the ratio log_b x / log_2 x is the same number for every x.

Input size → what's feasible: any x up to 10¹² → ratio unchanged, which is why Big-O ignores the base.

ln and e: e ≈ 2.71828… is a special constant that shows up naturally whenever something grows continuously in proportion to its own size (compound interest compounded infinitely often, radioactive decay, and — in this lesson — the harmonic series and Stirling's approximation). ln x = log_e x is "log base e", called the natural log. You rarely need to compute with e by hand; just recognise it as "the natural base for continuous growth", the same way 2 is the natural base for "things that double".

In Dart: e as the limit of (1 + 1/n)ⁿ, ln as the inverse of eˣ (math.exp / math.log), and Stirling's n! ≈ √(2πn)(n/e)ⁿ checked in log-space.

Input size → what's feasible: n = 10⁶ in the limit already gives 5 correct digits of e; Stirling is for n ≥ 10 (error under 1%) — and you never build n! itself, only ln n!.

In Dart: lg* as "apply lg until the value is ≤ 1", plus the digit-count formula behind the "19,729 digits" and "301 million digits" claims.

Input size → what's feasible: 2⁶⁵⁵³⁶ is far too big for a double (max ≈ 1.8·10³⁰⁸) — so we reduce it by one lg by hand; BigInt can still hold it (19,729 digits).

3. Floors, ceilings & mod

In Dart: ⌊x⌋ is x.floor(), ⌈x⌉ is x.ceil(); for integers ⌊n/2⌋ = n ~/ 2 and ⌈n/2⌉ = (n + 1) ~/ 2. a mod n is Dart's %, and the identity a mod n = a − n⌊a/n⌋ is checked with negative a too.

Input size → what's feasible: a, b, x up to 10⁹ → all O(1); ~/ truncates toward 0, so for negative numbers it is NOT floor — use .floor() or %.

4. The growth race: which function wins?

In Dart: the nine cost functions as Dart expressions; to compare 2ⁿ and n! without overflow the program compares log₂ of each (lg(n!) = Σ lg k), at n = 100 and n = 1000, and shows doubling n multiplies n² by 4 and n³ by 8.

Input size → what's feasible: n = 100 and 1000 are the "big enough" sizes where the ordering 1 < lg n < √n < n < n lg n < n² < n³ < 2ⁿ < n! is already final (at n = 10 it is not: √10 < lg 10).

To make the race concrete: suppose your computer does 100,000,000 (10⁸) basic operations per second. If your algorithm's cost matches one of these functions, here is the largest input size you could finish in exactly one second (every number below is computed and verified in verify/m01.dart). (You will see the notation O(...) used as a column label below before it is formally defined in Section 5 — for now just read O(f(n)) as "the cost is, roughly, the function f(n)"; the precise definition is coming.)

In Dart: the table above computed by largestN(cost, hi): a binary search for the biggest n whose cost fits in the 10⁸-operation budget (cost must increase with n). Doubling the budget is also tested.

Input size → what's feasible: binary search over [1, hi] takes ≤ 60 cost evaluations, so it is instant; the bound hi must keep the cost inside a 64-bit int (n³ → hi = 10⁶).

5. Big-O, Θ, Ω: the sandwich picture

In Dart: the definitions as checkers: isBigO / isOmega / isTheta test f(n) ≤ c·g(n) (or ≥) for every n from n₀ upward. A program can only test a finite range, so it can refute bad witnesses (n₀ = 2 fails) but a proof still needs algebra.

Input size → what's feasible: witnesses c₁ = 1, c₂ = 2, n₀ = 4 for f(n) = n² + 3n; test range n ≤ 10⁵ (10⁵ steps) is plenty to expose a wrong constant.

6. Summations (Σ)

In Dart: Σ is a for loop with a running total; an empty range adds nothing. For a sequence a₁…aₙ written in math notation (1-indexed) the Dart list is a[0]…a[n-1], so aᵢ is a[i - 1].

Input size → what's feasible: n ≤ 10⁸ → a plain loop is fine (~1 s); n = 10¹⁸ or millions of queries → you need a closed form (next sections).

6.1 Arithmetic series: 1 + 2 + 3 + … + n

As a 9-year-old, Carl Friedrich Gauss was reportedly asked to add 1 to 100 by hand — and instantly answered 5050 by pairing the first and last numbers: 1+100=101, 2+99=101, 3+98=101… fifty pairs, each summing to 101.

There is a similar closed form for the sum of squares (Gauss's pairing does not apply to it; it is proved by induction in the same style as Section 8): Σ_{i=1}^{n} i² = n(n+1)(2n+1)/6. For n=10 that's 10·11·21/6 = 385, matching 1+4+9+…+100 exactly.

In Dart: Gauss's pairing (n/2 pairs each worth n + 1), the closed form n(n+1)/2 for n = 0…200 and the sum of squares n(n+1)(2n+1)/6 for n = 0…100, each compared with the real loop.

Input size → what's feasible: n ≤ 3·10⁹ → n(n+1) still fits a 64-bit int (≈ 9·10¹⁸) and the O(1) formula beats the O(n) loop; for Σi² the product n(n+1)(2n+1) fits up to n ≈ 1.6·10⁶.

6.2 Geometric series: 1 + 2 + 4 + … and 1 + ½ + ¼ + …

A geometric series multiplies by a fixed ratio each step instead of adding a fixed amount. When the ratio is exactly 2, you get exactly the chessboard staircase from Section 1:

When the ratio is a fraction less than 1, the staircase shrinks instead of grows — and something remarkable happens: it never exceeds a fixed ceiling, no matter how many terms you add. (New symbol: ∞, "infinity", is not a number you can reach — it just means "and keep going, forever, with no last term." Writing ∞ on top of a Σ, as in Σ_{k=0}^{∞}, means "add up one term for every whole number k = 0, 1, 2, 3, … without ever stopping.")

In Dart: the staircase Σ 2ᵏ = 2ⁿ⁺¹ − 1, the "n bits hold 0…2ⁿ−1" subset-sum claim for {1, 2, 4, 8}, the general ratio formula (xⁿ⁺¹ − 1)/(x − 1) (exact, with BigInt) and the infinite series 1/(1−x) by summing 2000 terms.

Input size → what's feasible: n ≤ 61 for base 2 in a plain int; other bases or larger n → BigInt; infinite series: 2000 terms is enough when |x| ≤ 0.9 (0.9²⁰⁰⁰ ≈ 10⁻⁹²).

6.3 The harmonic series: 1 + ½ + ⅓ + … ≈ ln n

In Dart: Hₙ as a loop, the bound ln(n+1) ≤ Hₙ ≤ ln n + 1 for every n ≤ 5000, and the doubling-block split ([1,1], [2,2], [3,4], [5,8], …) where every block adds at most 1.

Input size → what's feasible: n ≤ 10⁷ → summing 1/k is a fast loop (error ≈ 10⁻⁹); Hₙ ≈ 16.7 at n = 10⁷, so it never gets large; the block split needs ⌈lg n⌉ + 1 = 25 blocks there.

6.4 Telescoping sums

Some sums collapse almost entirely when you rewrite each term as a difference, because the "middle" of each term cancels the "start" of the next one — like a collapsible telescope sliding shut.

In Dart: the partial-fraction identity 1/(k(k+1)) = 1/k − 1/(k+1), the sum 1 − 1/(n+1) for n up to 500, and the general rule Σ(aₖ − aₖ₋₁) = aₙ − a₀ on a concrete list.

Input size → what's feasible: n up to 10⁸ → the closed form is O(1); the loop would also work but accumulates rounding error in double.

6.5 Bounding a sum by an integral, and splitting a sum

Two more tools, used constantly to get quick Θ-bounds without finding an exact closed form:

In Dart: the two integral sandwiches with exact antiderivatives (x³/3 for the increasing f(x) = x², ln x for the decreasing f(x) = 1/x), tested for m = 2…10 and n up to 200, and the harmonic bound they imply.

Input size → what's feasible: any n: numerical integration is not needed — you use the antiderivative; tests here use n ≤ 200 (≈ 2000 loop steps).

6.6 From nested loops to Σ: counting operations

This is the single most practical use of summations in this whole course: counting exactly how many times a piece of code runs.

In Dart: the nested loop itself, its Σ (n − i + 1) form and n(n+1)/2, all compared for n = 1…60 and n = 1000 (500 500 iterations).

Input size → what's feasible: n ≤ 10⁴ → the brute-force count is fine (≈ 5·10⁷ steps); n = 10⁵ → 5·10⁹ steps is too slow, use the formula.

7. Recurrences preview: T(n) = 2T(n/2) + n

In Dart: T(n) = 2T(n/2) + n as a recursive function, the same with a memo table, and the closed form n·lg n + n (lg n is j for n = 2ʲ); the tree for n = 16 has lg n + 1 = 5 levels of exactly n work.

Input size → what's feasible: n = 2²⁰ → recursion depth only 21 (safe) and 2²¹ calls; n must be a power of two for this exact formula.

8. Proof by induction: dominoes

In Dart: what the proof says, executed: the base case n = 1, then for k = 1…500 the hypothesis, the algebra step k(k+1) + 2(k+1) = (k+1)(k+2) and the step P(k) + (k+1) = P(k+1). (Checking 500 cases is evidence, not proof — the induction argument is what covers every n.)

Input size → what's feasible: k ≤ 500 here; the proof itself covers every n ≥ 1.

Quiz

Interview questions

Cheat sheet