64. Which summation and logarithm identities come up most often in algorithm analysis?
EasyAlgorithm analysis
Technical
Show model answer
Arithmetic series: 1 + 2 + ... + n = n(n+1)/2 = Θ(n²). Sum of squares: Θ(n³), and in general the sum of i^k for i up to n is Θ(n^(k+1)). Geometric series: 1 + r + ... + r^n = (r^(n+1) - 1)/(r - 1), which is Θ(r^n) for r > 1 and Θ(1) for 0 < r < 1. Harmonic series: 1 + 1/2 + ... + 1/n ≈ ln n.
Logarithms: log(ab) = log a + log b, log(a^k) = k log a, log_b n = log n / log b (so the base is a constant factor and is dropped in Big-O), a^(log_b n) = n^(log_b a), and log(n!) = Θ(n log n). The last one is why comparison sorting has an n log n lower bound.