0 · Math toolkit: logs, exponents, sums

In one sentence

Algorithm analysis keeps asking two questions: "how many times can I halve this?" (that's a logarithm) and "what do all these loop steps add up to?" (that's a sum). This page gives you the handful of rules that answer both.

Everyday analogy

Logarithm = the "how many folds" number. Fold a 64-page newspaper in half, again and again, until one page is left. You fold it 6 times, so $\log_2 64 = 6$ . A log counts how many halvings (or doublings) it takes.
Sum = the till receipt. Each loop iteration adds an item to the bill. The closed-form formula is the total printed at the bottom, so you don't have to add the items one by one.

Key rules

Rule	Formula	Plain words
Definition	$\log_b x = y \iff b^y = x$	"What power of $b$ gives $x$ ?"
Product	$\log_b(xy) = \log_b x + \log_b y$	multiply inside → add outside
Quotient	$\log_b(x/y) = \log_b x - \log_b y$	divide inside → subtract outside
Power	$\log_b(x^a) = a\log_b x$	exponent jumps out to the front
Undo	$b^{\log_b x} = x$	a power and a log cancel
Change base	$\log_c x = \dfrac{\log_b x}{\log_b c}$	all logs differ only by a constant
Swap trick	$a^{\log_b c} = c^{\log_b a}$	handy in recurrences
Exponents	$2^a\cdot 2^b = 2^{a+b}$ , $(2^a)^b = 2^{ab}$
Arithmetic sum	$\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$	$\Theta(n^2)$
Squares	$\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$	$\Theta(n^3)$
Geometric ( $r\ne1$ )	$\sum_{i=0}^{k} r^i = \dfrac{r^{k+1}-1}{r-1}$
Powers of 2	$\sum_{i=0}^{k} 2^i = 2^{k+1}-1$	"the next power, minus one"
Shrinking geometric ( $0<r<1$ )	$\sum_{i=0}^{\infty} r^i = \dfrac{1}{1-r}$	a constant
Harmonic	$\sum_{i=1}^{n} \dfrac1i \approx \ln n$	$\Theta(\log n)$
Constant	$\sum_{i=1}^{n} c = cn$

Notation in this course: $\lg n = \log_2 n$ , $\ln n = \log_e n$ . In Big-O the base doesn't matter (change-base rule).

Logs as halving: the staircase

Step	0	1	2	3	4	5	6
Size	64	32	16	8	4	2	1

6 halvings reach 1, so $\log_2 64 = 6$ . Double $n$ and you add just one step. That's why $\log n$ grows so slowly.

$n$	8	1 024	1 048 576 (≈ a million)	≈ a billion
$\log_2 n$	3	10	20	30

Gauss's pairing trick for $1+2+\dots+n$ (here $n = 8$ )

 1   2   3   4
 8   7   6   5      ← same numbers written backwards
---------------
 9   9   9   9      ← every pair sums to n+1

4 pairs × 9 = 36 = $\frac{8\cdot 9}{2}$ . In general, $n/2$ pairs of $(n+1)$ give $\frac{n(n+1)}{2}$ .

Powers of 2: each term beats everything before it

1 + 2 + 4 + 8 = 15        next term = 16 = 15 + 1
■ ■■ ■■■■ ■■■■■■■■

So $1 + 2 + \dots + 2^k = 2^{k+1}-1$ . The largest term dominates: the total is less than twice the last term.

Common mistakes

$\log(a + b) \ne \log a + \log b$ . Only products split.
$(\log n)^2 \ne \log(n^2)$ . The first is "log squared"; the second equals $2\log n$ .
$\sum_{i=1}^{n} i$ is not $n$ . It's about $n^2/2$ .
Off-by-one in sums: $\sum_{i=0}^{k} 2^i$ has $k+1$ terms.

Mastery check

Solve without hints, then explain in your own words

(a) Find a closed form for $\sum_{i=1}^{n}(3i - 1)$ and check it with $n = 4$ .

(b) How many times can you halve 4096 before reaching 1?

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

See it move

Desmos: plot $\log_2 x$ , $\sqrt x$ and $x$ together to see which grows faster.

References

Lecture06 Algorithm Analysis: Mathematical Background: Slides 13–21 (logarithms), 22–26 (series).
CLRS 4e §3.3 (standard functions: logs, exponentials) and Appendix A (summations, A.1–A.2).

0 · Math toolkit: logs, exponents, sums

Everyday analogyCopy Anchor Link

Key rulesCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answers

See it moveCopy Anchor Link