Week 2: Analysis of Algorithms (45)

Logarithms
- log_b (xy) = log_b x + log_b y
- log_b (x/y) = log_b x - log_b y
- log_b x^a = a log_b x
- log_a x = log_b x · (log_c b / log_c a)
Exponentials
- a^(b+c) = a^ba^c
- a^bc = (a^b)^{^c}
- a^b / a^c = a^(b-c)
- b = a^log_ab
- b^c = a^c·log_ab
Proof techniques
Summation (addition of sequences of numbers)
Basic probability (for average case analysis, randomised algorithms)