Math Quick Reference
This page contains some mathematical definitions and facts that will be useful during the course.
Exponents
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)
Logarithms
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Κ°
Logic rules
logic rule and application: If A is true, then B is true. A is true. Therefore, B is true.
logic rule and application: If A is true, then B is true. B is not true. Therefore, A is not true.
Asymptotic bounds
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 π(π)
Useful fact:Β
For every b > 1 and every x > 0, we have log_b n = O(n^x) [from page 41 of Algorithm Design text]