Math Cheatsheet

A refresher of some math rules.

You do not need heavy math for this course. But a few rules show up again and again when we count steps and compare running times. Most of you learned these years ago, so this page is a quick refresher.

You can also use Desmos to visualize the math formulas!

1. Exponents (powers)

\(b^n\) means “multiply \(b\) by itself \(n\) times”: \(2^4 = 2 \times 2 \times 2 \times 2 = 16\).

Rule	In words	Example
\(b^m \cdot b^n = b^{m+n}\)	Multiplying powers adds the exponents	\(2^3 \cdot 2^4 = 2^7 = 128\)
\(\dfrac{b^m}{b^n} = b^{m-n}\)	Dividing powers subtracts the exponents	\(\dfrac{2^5}{2^2} = 2^3 = 8\)
\((b^m)^n = b^{mn}\)	A power of a power multiplies the exponents	\((2^3)^2 = 2^6 = 64\)
\(b^0 = 1\)	Anything (except 0) to the power 0 is 1	\(7^0 = 1\)
\(b^{-n} = \dfrac{1}{b^n}\)	A negative exponent means “one over”	\(2^{-3} = \tfrac{1}{8}\)
\(b^{1/2} = \sqrt{b}\)	A fractional exponent is a root	\(9^{1/2} = 3\)

The one we use most. Doubling the input of an exponential algorithm squares its cost:

\[2^{2n} = (2^n)^2\]

So if \(n = 10\) takes 1 second, \(n = 20\) takes about \(1024\) seconds, not 2 seconds. That is why \(O(2^n)\) is hopeless.

Powers of 2 calculations

\(n\)	1	4	8	10	16	20	30
\(2^n\)	2	16	256	1,024	65,536	~1 million	~1 billion

2. Logarithms

A logarithm is just an exponent asked backwards.

\[\log_b x = y \quad\text{means exactly}\quad b^y = x\]

“\(\log_2 x\)” reads as: how many times do I have to double 1 to reach \(x\)? Equivalently: how many times can I halve \(x\) before I get down to 1?

\(\log_2 8 = 3\) because \(2^3 = 8\). And indeed \(8 \to 4 \to 2 \to 1\) is 3 halvings.

\(n\)	8	64	1,024	1 million	1 billion
\(\log_2 n\)	3	6	10	~20	~30

Look at that last column: a billion items, and binary search needs only about 30 steps.

Log rules

Rule	In words	Example
\(\log_b(xy) = \log_b x + \log_b y\)	A product inside becomes a sum outside	\(\log_2 (4 \cdot 8) = 2 + 3 = 5\)
\(\log_b\!\left(\dfrac{x}{y}\right) = \log_b x - \log_b y\)	A quotient becomes a difference	\(\log_2\!\left(\tfrac{16}{2}\right) = 4 - 1 = 3\)
\(\log_b(x^k) = k \log_b x\)	An exponent inside comes out in front	\(\log_2 (8^2) = 2 \cdot 3 = 6\)
\(\log_b 1 = 0\)	You need 0 doublings to reach 1	\(\log_2 1 = 0\)
\(\log_b b = 1\)	One doubling reaches \(b\)	\(\log_2 2 = 1\)
\(b^{\log_b x} = x\)	Exponentials and logs undo each other	\(2^{\log_2 5} = 5\)
\(\log_b x = \dfrac{\log_c x}{\log_c b}\)	Change of base	\(\log_2 x = \dfrac{\ln x}{\ln 2}\)
\(\log_b a = \dfrac{1}{\log_a b}\)	Inverse of base	\(\log_2 5 = \dfrac{1}{\log_5 2}\)

3. Adding up \(1 + 2 + \dots + n\)

\[1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\]

Why it works. Write the sum forwards and backwards and add them column by column:

\[ \begin{array}{rcl} S &=& 1 + 2 + \cdots + (n-1) + n \\ S &=& n + (n-1) + \cdots + 2 + 1 \\ \hline 2S &=& \underbrace{(n+1) + (n+1) + \cdots + (n+1)}_{n \text{ copies}} \;=\; n(n+1) \end{array} \]

So \(S = \dfrac{n(n+1)}{2}\).

Example. \(1 + 2 + \cdots + 100 = \dfrac{100 \cdot 101}{2} = 5{,}050\).

Two relatives

Sum	Formula	Big O
\(\underbrace{c + c + \cdots + c}_{n \text{ times}}\)	\(cn\)	\(O(n)\)
\(1 + 2 + 3 + \cdots + n\)	\(\dfrac{n(n+1)}{2}\)	\(O(n^2)\)

4. Factorials

\(n!\) (“n factorial”) means \(n \times (n-1) \times \cdots \times 2 \times 1\), with \(0! = 1\) by convention.

\[5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\]

It counts orderings: the number of different ways to line up \(n\) distinct things. 5 drivers can be visited in 120 different orders.

\(n\)	5	10	15	20
\(n!\)	120	3.6 million	1.3 trillion	\(2.4 \times 10^{18}\)

\(n!\) grows faster than \(2^n\), which grows faster than \(n^2\).

Choosing pairs and groups: \(\binom{n}{k}\)

\(\binom{n}{k}\) (read “n choose k”) is the number of ways to pick \(k\) items out of \(n\) when order does not matter:

\[\binom{n}{k} = \frac{n!}{k!\,(n-k)!}\]

The case we actually use is \(k = 2\): the number of pairs you can form from \(n\) things:

\[\binom{n}{2} = \frac{n(n-1)}{2}\]