Math Quick Reference

This page contains some mathematical definitions and facts that will be useful during the course.

Exponent operator

𝑥ᵃ is the product obtained by multiplying 𝑥 with itself 𝑎 times.

Product Rule

𝑥ᵃ𝑥ᵇ=𝑥ᵃ⁺ ᵇ

Quotient Rule

Power of a power

(xᵃ)ᵇ=xᵃᵇ

Distributive property of exponents

(xy)ᵃ=xᵃyᵃ

Distributive property of exponents (applied to fractions)

Logarithm function

logb(a) is the unique number 𝑐 such that bᶜ=𝑎.

Informally: the number of times you can divide a by b until you get to 1.

Log Product Rule

log(𝑥𝑦)=log(𝑥)+log(𝑦), for any base

Log Exponent Rule

log(𝑥ᵏ)=𝑘 log(𝑥)

(any base)

Inverse Property

logb(a) and bᵃ are inverses

f(x) and g(x) are inverses if f○g (x) = g○f (x) = x.

This means:

Change in Base Rule

This means: logs in any two bases are proportional: logₐn = (logₐ b)(logb a).

And therefore, when using asymptotic bounds, it’s OK not to specify base (though generally assume log₂ if not specified.)

Log “Flipping” Rule

Binary Trees

The height of a binary tree is the #edges on the longest path from the root to a leaf. For example, a tree that is just the root has height 0.

For complete binary trees (every level is filled, except maybe the last) with all possible vertices in the final level:

• if there are n leaves, the height of the tree is log₂n

• if the height of the tree is h, then the number of leaves is 2ʰ

modus ponens

logic rule and application: If A is true, then B is true. A is true. Therefore, B is true.

modus tollens

logic rule and application: If A is true, then B is true. B is not true. Therefore, A is not true.

big-O asymptotic upper bound

𝑓(𝑛) is 𝑂(𝑔(𝑛)) if there exists 𝑐,n₀≥0 such that 𝑓(𝑛)≤𝑐𝑔(𝑛) for all 𝑛≥n₀

Informally: 𝑓(𝑛) grows at a rate that is no faster than 𝑔(𝑛)

big-Ω asymptotic lower bound

𝑓(𝑛) is Ω(𝑔(𝑛)) if there exists 𝑐>0,𝑛0≥0 such that 𝑓(𝑛)≥𝑐𝑔(𝑛) for all 𝑛≥𝑛0

Informally: 𝑓(𝑛) grows at a rate that is no slower than 𝑔(𝑛)

big-Θ asymptotic tight bound

𝑓(𝑛) is Θ(𝑔(𝑛)) if there exists 𝑐₁ > 0, 𝑐₂, n₀ ≥ 0 such that 𝑐₁ 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐₂ 𝑔(𝑛) for all 𝑛 ≥ n₀

Informally: 𝑓(𝑛) grows at the same rate as 𝑔(𝑛)

For every b > 1 and every x > 0, we have log_b n = O(n^x) [from page 41 of Algorithm Design text]

Useful fact: