Week 4: Complexity of Recursive Methods

Question 1

Exponentials

Answer 1

a⁰ = 1
a¹ = a
a^-1 = 1/a
(a^m)ⁿ = a^mn
a^maⁿ = a^m+n

for all n, a ≥ 1 the function aⁿ is monotonically increasing in n (always increasing or constant)

Question 2

Logarithms

Answer 2

a = b^log_ba

log_c(ab) = log_ca + log_cb

log_ba = log_ca/log_cb

log_b(1/a) = -log_ba

log_ba = 1/log_ab

a^log_bc = c^log_ba

where log base ≠ 1

Question 3

Factorials

Answer 3

n! = 1 x 2 x 3 …. n

weak upper bound n! ≤ nⁿ

1 x 2 x 3 … n < n x n x n …

Question 4

Stirling’s Approximation

Answer 4

n! = √2π (n/e)ⁿ(1 + Θ(1/n))

Question 5

Sums

Answer 5

​a₁ + a₂ + … + a_n k=1 ∑n​ a_k

if n = 0, sum is 0​

lim n→∞ ​k=1 ∑n​ a_k

If the limit exists, the series converges, else it diverges​