Summations you will reuse forever

The four sums that appear in almost every analysis

Running-time analysis is mostly counting, and counting collapses into a handful of summations. Memorize these closed forms — you will reach for them in insertion sort, merge sort, quicksort, heaps, and amortized analysis.

Arithmetic series. $$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}=\Theta (n^2).$$ This is the cost of insertion sort's worst case (pass $i$ does up to $i$ comparisons, summed over passes).

Sum of squares. $$\sum _{k=1}^n{k}^2=\frac{n(n+1)(2n+1)}{6}=\Theta (n^3).$$

Finite geometric series (for $x\ne 1$): $$\sum _{k=0}^n{x}^k=\frac{x^{n+1}-1}{x-1}.$$ When $|x|<1$ the infinite tail converges: ${\sum }_{k=0}^{\infty }{x}^k=\frac{1}{1-x}$. Geometric series drive divide-and-conquer recurrences and amortized doubling.

Harmonic series. $$H_n=\sum _{k=1}^n\frac{1}{k}=\ln n+O(1),$$ tightly: $\ln (n+1)\le H_n\le \ln n+1$, and $H_n\to \ln n+\gamma$ with Euler's constant $\gamma \approx 0.5772$. The harmonic series is the source of the $\lg n$ factor in randomized quicksort (Module 2).

Two manipulations worth knowing

Linearity: $\sum (c{a}_k+b_k)=c\sum a_k+\sum b_k$, and asymptotically $\sum \Theta (f(k))=\Theta (\sum f(k))$ for monotone $f$.

Telescoping: ${\sum }_{k=1}^n(a_k-a_{k-1})=a_n-a_0$ — every interior term cancels. For example ${\sum }_{k=1}^n\frac{1}{k(k+1)}=\sum (\frac{1}{k}-\frac{1}{k+1})=1-\frac{1}{n+1}$.

When is a geometric bound valid? (the trap)

A standard way to bound a sum is: if $a_{k+1}/a_k\le r$ for some constant $r<1$, then ${\sum }_{k=0}^n{a}_k\le \frac{a_0}{1-r}$ — the whole sum is $O(a_0)$, a constant times the first term.

The trap: ratio $<1$ is not enough. You need ratio $\le r$ for a fixed $r$ strictly below 1. The harmonic series is the cautionary tale: its term ratio is $\frac{1/(k+1)}{1/k}=\frac{k}{k+1}<1$ for every $k$ — yet $H_n$ diverges ($\to \infty$). The reason: that ratio creeps toward $1$ as $k$ grows, so no single $r<1$ dominates it. Bounding $H_n$ by a geometric series gives a flatly wrong (finite) answer; the right tool is integral approximation: $H_n\le 1+{\int }_1^n\frac{dx}{x}=1+\ln n$.

Worked example — verify a closed form empirically. Before trusting a closed form in a proof, sanity-check it on a concrete $n$. For $n=100$: the loop ${\sum }_{k=1}^{100}k$ gives $5050$, and $\frac{100\cdot 101}{2}=5050$. For the geometric sum with $x=2,n=10$: the loop gives $2047$, and $\frac{2^{11}-1}{2-1}=2047$. The exercises below run exactly this check.