Tutorial by Examples

The sum 1 + 2 + 3 + ... + n Simplifies to n(n+1) / 2. Notice that this quantity is Θ(n2). This shortcut arises frequently in the analysis of algorithms like insertion sort or selection sort. Numbers of the form n(n+1)/2 are called the triangular numbers.

The sum 20 + 21 + 22 + ... + 2n-1 simplifies to 2n - 1. This explains why the maximum value that can be stored in an unsigned 32-bit integer is 232 - 1.

The sum of the geometric series r0 + r1 + r2 + ... + rn-1 In the case where r ≠ 1, simplifies to (rn - 1) / (r - 1). If r < 1, this sum is bounded from above by 1 / (1 - r). If r = 1, this sum is rn.

Here we consider sums of the form a + b + a + b + ... a vs. a + b + a + b + ... b To visualize these sums, imagine a section of fence alternating between posts and rails. Three scenarios are possible. Imagine a section of fence with posts at each end, connected by rails. n rails require...

The Fibonacci numbers are defined inductively as F0 = 0 F1 = 1 Fn+2 = Fn + Fn+1 The sum of the first n+1 Fibonacci numbers is given by F0 + F1 + F2 + ... + Fn = Fn+2 - 1. This summation arises, among other places, in the analysis of Fibonacci heaps, where it's used to provide a lower b...

The summation 1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n is equal to the nth harmonic number, denoted Hn. The nth harmonic number obeys the inequalities ln (n + 1) ≤ Hn ≤ (ln n) + 1 and therefore Hn = Θ(log n). The harmonic numbers often arise in the analysis of algorithms, with randomized quicks...

The summation 1/1 + 1/4 + 1/9 + 1/16 + ... out to infinity converges to π2 / 6, and therefore any summation of the form 1/1 + 1/4 + 1/9 + 1/16 + ... + 1/n2 is Θ(1).