1. What is a Sequence?
A sequence is just an ordered list of numbers that follows a pattern. That's it. Nothing fancy -- it's a list where each number has a position.
Counting numbers: 1, 2, 3, 4, 5, 6, 7, ...
Even numbers: 2, 4, 6, 8, 10, 12, ...
Odd numbers: 1, 3, 5, 7, 9, 11, ...
Powers of 2: 1, 2, 4, 8, 16, 32, 64, ...
Squares: 1, 4, 9, 16, 25, 36, ...
Multiples of 5: 5, 10, 15, 20, 25, ...
Naming the Terms
We use an to mean "the nth term." The subscript tells you the position:
a2 = second term
a3 = third term
...
an = the nth term (the general term)
For the sequence 2, 4, 6, 8, 10, ...
- a1 = 2 (first term)
- a2 = 4 (second term)
- a3 = 6 (third term)
- an = 2n (formula: to get the nth term, multiply n by 2)
Let's verify: a5 = 2(5) = 10. Looking at the sequence: 2, 4, 6, 8, 10. Correct!
Two Types of Formulas
There are two ways to describe a sequence:
| Type | How it Works | Example (for 2, 4, 6, 8, ...) |
|---|---|---|
| Explicit formula | Gives you any term directly from its position | an = 2n (plug in n, get the answer) |
| Recursive formula | Gives you the next term from the previous one | an = an-1 + 2, where a1 = 2 |
Explicit formula is like array access -- O(1), instant lookup:
def get_term(n):
return 2 * n # Instant! Just plug in nRecursive formula is like a linked list -- you have to walk through from the start:
def get_term(n):
if n == 1: return 2
return get_term(n - 1) + 2 # Need all previous terms!Finite vs Infinite Sequences
- Finite sequence: Has a definite end. Example: 1, 2, 3, 4, 5 (5 terms)
- Infinite sequence: Goes on forever. Example: 1, 2, 3, 4, 5, ... (the "..." means it continues)
2. What is a Series?
A series is what you get when you add up the terms of a sequence. A sequence is a list; a series is a sum.
| Sequence (a list) | Series (a sum) |
|---|---|
| 1, 2, 3, 4, 5 | 1 + 2 + 3 + 4 + 5 = 15 |
| 2, 4, 6, 8 | 2 + 4 + 6 + 8 = 20 |
| 1, 2, 4, 8 | 1 + 2 + 4 + 8 = 15 |
| 3, 3, 3, 3, 3 | 3 + 3 + 3 + 3 + 3 = 15 |
When you write a loop, you create a sequence. When you count the total work that loop does, you compute a series.
# The loop variable i creates the sequence: 0, 1, 2, 3, 4
for i in range(5):
# If we do 'i' units of work each iteration,
# the TOTAL work is the SERIES: 0 + 1 + 2 + 3 + 4 = 10
for j in range(i):
do_something() # This runs 10 times total, not 5!Understanding series = understanding how to count total iterations of nested loops.
Partial Sums
A partial sum Sn is the sum of the first n terms:
- S1 = a1 (just the first term)
- S2 = a1 + a2 (first two terms)
- S3 = a1 + a2 + a3 (first three terms)
- Sn = a1 + a2 + ... + an (first n terms)
S1 = 1
S2 = 1 + 2 = 3
S3 = 1 + 2 + 3 = 6
S4 = 1 + 2 + 3 + 4 = 10
S5 = 1 + 2 + 3 + 4 + 5 = 15
These numbers (1, 3, 6, 10, 15) are called triangular numbers. They form the shape of a triangle when you stack dots. We'll see a formula for these soon.
3. Arithmetic Sequences
An arithmetic sequence (also called an arithmetic progression or AP) is a sequence where you get each new term by adding the same number every time. That number is called the common difference (d).
a1, a1 + d, a1 + 2d, a1 + 3d, ...
Subtract consecutive terms. If the difference is always the same, it's arithmetic.
3, 7, 11, 15, 19, ...
7 - 3 = 4, 11 - 7 = 4, 15 - 11 = 4, 19 - 15 = 4
Common difference d = 4. Arithmetic!
10, 7, 4, 1, -2, -5, ...
7 - 10 = -3, 4 - 7 = -3, 1 - 4 = -3
Common difference d = -3. Still arithmetic! (d can be negative)
1, 2, 4, 8, 16, ...
2 - 1 = 1, 4 - 2 = 2, 8 - 4 = 4 -- differences are NOT the same.
Not arithmetic! (This is geometric -- we'll cover that in section 7)
The nth Term Formula
To find any term without listing them all, use this formula:
Where:
• a1 = first term
• d = common difference (subtract any term from the next)
• n = which term you want
• an = the value of that term
Why (n - 1) and Not Just n?
This is the most common mistake, so let's build the formula from scratch to see why:
Start with a1 = 3, d = 4. Let's write out each term:
| Term | Value | How We Got It | How Many Times We Added d |
|---|---|---|---|
| a1 | 3 | 3 (just the start) | 0 times |
| a2 | 7 | 3 + 4 | 1 time |
| a3 | 11 | 3 + 4 + 4 | 2 times |
| a4 | 15 | 3 + 4 + 4 + 4 | 3 times |
| a5 | 19 | 3 + 4 + 4 + 4 + 4 | 4 times |
| an | ? | 3 + 4 × (n - 1) | (n - 1) times |
Pattern: To reach term n, you add d exactly (n - 1) times because the first term doesn't require any addition.
So: an = 3 + 4(n - 1) = 3 + 4n - 4 = 4n - 1
The formula is an = a1 + (n - 1)d, NOT a1 + nd.
Think of it like a fence: to make a fence with 5 posts, you need 4 gaps between them. To get to the 5th term, you make 4 jumps of d.
Sequence: 5, 8, 11, 14, 17, ...
Step 1: Find a1 = 5
Step 2: Find d = 8 - 5 = 3
Step 3: Apply formula: a50 = 5 + (50 - 1)(3) = 5 + 49(3) = 5 + 147 = 152
Without the formula, you'd have to list all 50 numbers. With it, instant!
Sequence: 3, 7, 11, 15, ... Which term is 100? (or: does 100 even appear?)
a1 = 3, d = 4. Set an = 100:
100 = 3 + (n - 1)(4)
100 = 3 + 4n - 4
100 = 4n - 1
101 = 4n
n = 101/4 = 25.25
Since n must be a whole number, 100 is NOT in this sequence. The 25th term is 99 and the 26th is 103.
Array memory addresses form an arithmetic sequence! If an array starts at memory address 1000 and each element takes 4 bytes:
# Element addresses: 1000, 1004, 1008, 1012, ...
# a₁ = 1000, d = 4
# Address of element n: 1000 + (n-1) × 4
# THIS is why array access is O(1) -- it's just plugging into a formula!4. Arithmetic Series (Sums)
An arithmetic series is the sum of an arithmetic sequence. Instead of listing the terms, we add them all up.
Sn = n/2 × (a1 + an) = n/2 × (first term + last term)
Or equivalently:
Sn = n/2 × (2a1 + (n - 1)d)
Use the first form when you know the last term. Use the second when you don't.
But where does this formula come from? Let's build it up intuitively in the next section.
Find the sum: 2 + 4 + 6 + 8 + 10
a1 = 2, an = 10, n = 5 terms
S5 = 5/2 × (2 + 10) = 2.5 × 12 = 30
Verify: 2 + 4 + 6 + 8 + 10 = 30. Correct!
5. The Gauss Trick & n(n+1)/2
This is the most important formula in algorithm analysis. Let's understand it deeply.
The Story
Legend says that when the mathematician Carl Friedrich Gauss was a schoolchild, his teacher told the class to add up all numbers from 1 to 100, expecting it to keep them busy. Young Gauss answered almost immediately: 5,050.
Here's how he did it:
We want: S = 1 + 2 + 3 + ... + 98 + 99 + 100
Step 1: Write the sum forwards and backwards
S = 1 + 2 + 3 + ... + 98 + 99 + 100
S = 100 + 99 + 98 + ... + 3 + 2 + 1Step 2: Add the two rows column by column
2S = 101 + 101 + 101 + ... + 101 + 101 + 101Every pair sums to 101! And there are 100 pairs.
Step 3: Solve
2S = 100 × 101 = 10,100
S = 10,100 / 2 = 5,050
The General Formula
The same trick works for 1 + 2 + 3 + ... + n:
1 + 2 + 3 + ... + n = n(n + 1) / 2
First term + last term = (1 + n) = (n + 1). Number of pairs = n/2. Product = n(n+1)/2.
Pair the terms from outside in:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
| |
└──────────────── 1 + 10 = 11 ──────────────────────────┘
| |
└──────────── 2 + 9 = 11 ──────────────────┘
| |
└──────── 3 + 8 = 11 ──────────┘
| |
└──── 4 + 7 = 11 ──┘
| |
5 + 6 = 115 pairs, each summing to 11 = 5 × 11 = 55
In general: n/2 pairs, each summing to (n + 1) = n(n+1)/2
1 + 2 + 3 + ... + 10:
n = 10 → 10(11)/2 = 110/2 = 55
1 + 2 + 3 + ... + 100:
n = 100 → 100(101)/2 = 10,100/2 = 5,050
1 + 2 + 3 + ... + 1000:
n = 1000 → 1000(1001)/2 = 1,001,000/2 = 500,500
0 + 1 + 2 + ... + (n-1):
This is the same as 1 + 2 + ... + (n-1) = (n-1)(n)/2 = n(n-1)/2
This version appears more often in code (0-indexed loops)!
In math, we usually sum from 1 to n: n(n+1)/2
In code, loops usually go from 0 to n-1: n(n-1)/2
Both are O(n²) -- the constant doesn't matter for Big-O.
6. Why n(n+1)/2 = O(n²)
This is exactly what the image you saw is about. Let's break it down completely.
The Setup: A Shrinking Inner Loop
Consider selection sort, or any algorithm where the inner loop does less work each iteration:
for i in range(n): # Outer: runs n times
for j in range(i, n): # Inner: runs (n-i) times each iteration
compare(arr[j]) # Some O(1) workHow many times does compare() run in total?
| i = | Inner loop runs | Times |
|---|---|---|
| 0 | j goes from 0 to n-1 | n |
| 1 | j goes from 1 to n-1 | n - 1 |
| 2 | j goes from 2 to n-1 | n - 2 |
| 3 | j goes from 3 to n-1 | n - 3 |
| ... | ... | ... |
| n-2 | j goes from n-2 to n-1 | 2 |
| n-1 | j goes from n-1 to n-1 | 1 |
So the total is:
This is just 1 + 2 + 3 + ... + n written backwards!
= n(n+1)/2
From Exact Count to Big-O
Now, n(n+1)/2 is an exact count. Let's expand it to see why it's O(n²):
= (n² + n) / 2
= n²/2 + n/2
In Big-O, we drop constants and lower-order terms:
• Drop the /2: it's a constant multiplier
• Drop the + n/2: it grows slower than n²
= O(n²)
Big-O cares about growth rate, not exact count. Let's see why the n/2 term doesn't matter as n gets large:
| n | n²/2 | n/2 | Total (n²/2 + n/2) | n/2 as % of total |
|---|---|---|---|---|
| 10 | 50 | 5 | 55 | 9.1% |
| 100 | 5,000 | 50 | 5,050 | 1.0% |
| 1,000 | 500,000 | 500 | 500,500 | 0.1% |
| 1,000,000 | 500,000,000,000 | 500,000 | 500,000,500,000 | 0.0001% |
As n grows, the n² term completely dominates. The n term becomes negligible. That's why O(n²/2 + n/2) = O(n²).
Algorithms That Use This Pattern
def selection_sort(arr):
n = len(arr)
for i in range(n): # n iterations
min_idx = i
for j in range(i+1, n): # (n-1) + (n-2) + ... + 1 = n(n-1)/2
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# Total comparisons: n(n-1)/2 = O(n²)def bubble_sort(arr):
n = len(arr)
for i in range(n): # n passes
for j in range(n-1-i): # (n-1) + (n-2) + ... + 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# Total comparisons: n(n-1)/2 = O(n²)def insertion_sort(arr):
for i in range(1, len(arr)): # n-1 iterations
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key: # Worst case: i comparisons
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# Worst case: 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)Whenever you see a loop pattern where the inner work counts down (or up) like n, n-1, n-2, ..., 1 -- you know instantly it's O(n²) because you're summing an arithmetic series, and the sum is n(n+1)/2.
7. Geometric Sequences
A geometric sequence (also called a geometric progression or GP) is a sequence where you get each new term by multiplying by the same number every time. That number is called the common ratio (r).
a1, a1×r, a1×r², a1×r³, ...
Divide consecutive terms. If the ratio is always the same, it's geometric.
2, 6, 18, 54, 162, ...
6/2 = 3, 18/6 = 3, 54/18 = 3, 162/54 = 3
Common ratio r = 3. Geometric!
100, 50, 25, 12.5, 6.25, ...
50/100 = 0.5, 25/50 = 0.5, 12.5/25 = 0.5
Common ratio r = 0.5. Geometric! (r can be a fraction)
1, -2, 4, -8, 16, ...
-2/1 = -2, 4/(-2) = -2, -8/4 = -2
Common ratio r = -2. Geometric! (r can be negative -- terms alternate sign)
| Arithmetic (AP) | Geometric (GP) | |
|---|---|---|
| Operation | Add the same number | Multiply by the same number |
| Growth | Linear (steady) | Exponential (explosive or decaying) |
| Example | 2, 5, 8, 11, 14 (d = 3) | 2, 6, 18, 54, 162 (r = 3) |
| 10th term | 2 + 9(3) = 29 | 2 × 3&sup9; = 39,366 |
| CS analogy | Linear search O(n) | Exponential blowup O(2n) |
The nth Term Formula
Where:
• a1 = first term
• r = common ratio (divide any term by the previous one)
• n = which term you want
Start with a1 = 2, r = 3:
| Term | Value | How We Got It | Times Multiplied by r |
|---|---|---|---|
| a1 | 2 | 2 (just the start) | 0 times |
| a2 | 6 | 2 × 3 | 1 time |
| a3 | 18 | 2 × 3 × 3 | 2 times |
| a4 | 54 | 2 × 3 × 3 × 3 | 3 times |
| an | ? | 2 × 3(n-1) | (n-1) times |
Same pattern as arithmetic: the (n - 1) is because the first term doesn't need any multiplication.
Sequence: 1, 2, 4, 8, 16, 32, ...
a1 = 1, r = 2
an = 1 × 2(n-1) = 2(n-1)
The 10th term: a10 = 29 = 512
The 20th term: a20 = 219 = 524,288
This is exponential growth -- it gets enormous fast!
Geometric sequences with r = 2 appear everywhere in CS:
- Binary tree levels: 1, 2, 4, 8, 16, ... nodes per level
- Recursive branching: Each call spawns 2 more → 2n total calls
- Dynamic array resizing: Capacity doubles: 1, 2, 4, 8, 16, ...
- Bit lengths: n bits can represent 2n values
You invest $1,000 at 8% annual interest. How much after 10 years?
Each year, your money is multiplied by 1.08 (original + 8%).
a1 = 1000, r = 1.08
After 10 years (11th term): a11 = 1000 × 1.0810 = 1000 × 2.159 = $2,158.92
Your money more than doubled! That's the power of geometric growth.
Geometric Decay (When |r| < 1)
When the common ratio is between -1 and 1 (exclusive), terms get smaller and smaller:
Half-life: 1000, 500, 250, 125, 62.5, ... (r = 0.5)
Each term is half the previous. Terms approach zero but never reach it.
In CS: Binary search cuts the problem in half each step. Starting with n elements, the remaining work is: n, n/2, n/4, n/8, ... This geometric decay is why binary search is O(log n)!
8. Geometric Series (Sums)
A geometric series is the sum of a geometric sequence.
Sn = a1 × (rn - 1) / (r - 1) (use when r > 1)
Sn = a1 × (1 - rn) / (1 - r) (use when |r| < 1 -- avoids negatives)
These are the same formula rearranged. Use whichever avoids negative numbers.
Where Does the Formula Come From?
Let's find S = 1 + 2 + 4 + 8 + 16 (geometric with a1 = 1, r = 2, n = 5)
Step 1: Write S
S = 1 + 2 + 4 + 8 + 16
Step 2: Multiply both sides by r (= 2)
2S = 2 + 4 + 8 + 16 + 32
Step 3: Subtract S from 2S
2S = 2 + 4 + 8 + 16 + 32
S = 1 + 2 + 4 + 8 + 16
─────────────────────────
S = 32 - 1 = 31Almost everything cancels! We're left with: 2S - S = 32 - 1
S = 25 - 1 = 32 - 1 = 31
Verify: 1 + 2 + 4 + 8 + 16 = 31. Correct!
In general: rS - S = a1(rn - 1), so S = a1(rn - 1)/(r - 1)
For the sum 1 + 2 + 4 + 8 + ... + 2(n-1):
S = (2n - 1) / (2 - 1) = 2n - 1
Examples:
- 1 + 2 + 4 = 2³ - 1 = 7
- 1 + 2 + 4 + 8 = 24 - 1 = 15
- 1 + 2 + 4 + 8 + 16 = 25 - 1 = 31
- 1 + 2 + 4 + ... + 128 = 28 - 1 = 255
- 8-bit max value: 1 + 2 + 4 + ... + 128 = 28 - 1 = 255
- 32-bit max unsigned: 232 - 1 = 4,294,967,295
- Binary tree nodes: A complete tree of height h has 1 + 2 + 4 + ... + 2h = 2(h+1) - 1 total nodes
- Merge sort calls: Total recursive calls in merge sort: 2k - 1 where k = log2(n)
A complete binary tree of height 4:
Level 0: 1 node (2&sup0;)
Level 1: 2 nodes (2¹)
Level 2: 4 nodes (2²)
Level 3: 8 nodes (2³)
Level 4: 16 nodes (24)
──────────────────────────
Total: 31 nodes = 25 - 1This is a geometric series: 1 + 2 + 4 + 8 + 16 = 25 - 1 = 31
Merge sort splits n elements in half each level. At each level, the total work is O(n):
Level 0: 1 chunk of size n → n work
Level 1: 2 chunks of size n/2 → n work
Level 2: 4 chunks of size n/4 → n work
...
Level k: n chunks of size 1 → n workThere are log2(n) levels, each doing n work:
Total = n × log2(n) = O(n log n)
The geometric sequence (1, 2, 4, 8, ...) describes how the number of chunks doubles at each level, while the size of each chunk halves.
9. Infinite Series & Convergence
What happens when you add up infinitely many terms? Sometimes the sum is finite (it converges), sometimes it blows up to infinity (it diverges).
Can infinitely many things add up to a finite number? Yes -- if each new thing is small enough. Think of it physically:
- Converges: Walk halfway to a wall, then half of what's left, then half again. Infinitely many steps, but you never pass the wall.
- Diverges: Stack bricks on top of each other, each the same size. Infinitely many bricks = infinite height.
The key question is: do the terms shrink fast enough? If each term is a fraction of the previous one (geometric with |r| < 1), they shrink fast enough. If the terms don't shrink, or shrink too slowly, the sum diverges.
Convergent Geometric Series
When |r| < 1, the terms get smaller and smaller, and the sum approaches a fixed value:
S∞ = a1 / (1 - r)
a1 = 1/2, r = 1/2
S∞ = (1/2) / (1 - 1/2) = (1/2) / (1/2) = 1
Let's see it converge:
| Terms Added | Sum | Distance from 1 |
|---|---|---|
| 1/2 | 0.5 | 0.5 |
| + 1/4 | 0.75 | 0.25 |
| + 1/8 | 0.875 | 0.125 |
| + 1/16 | 0.9375 | 0.0625 |
| + 1/32 | 0.96875 | 0.03125 |
| + 1/64 | 0.984375 | 0.015625 |
Each step gets closer to 1, but never exceeds it. With infinitely many terms, the sum equals exactly 1.
a1 = 1, r = 1/2
S∞ = 1 / (1 - 1/2) = 1 / (1/2) = 2
Imagine walking to a wall. First you cover half the distance, then half of what's left, then half again... You'll get arbitrarily close to the wall (sum = 2) but each step is half the previous.
Divergent Series
When |r| ≥ 1, the terms don't shrink, so the sum grows without bound:
1 + 2 + 4 + 8 + 16 + ... (r = 2) → Diverges! Each term is bigger than the last.
1 + 1 + 1 + 1 + ... (r = 1) → Diverges! Adding 1 forever gives infinity.
1 + 2 + 3 + 4 + ... (arithmetic, d = 1) → Diverges! Arithmetic series always diverge (unless d = 0).
Dynamic arrays (like Python lists or Java ArrayLists) use convergent geometric series for resizing:
# ArrayList doubles when full. Copy costs over n insertions:
# 1 + 2 + 4 + 8 + ... + n = 2n - 1 ≈ 2n
# Amortized cost per insertion: 2n / n = O(1)
#
# The key insight: the geometric sum 1 + 2 + 4 + ... + n
# is dominated by the LAST term (n), not the sum of all others.
# So the total copy work is only about 2n, giving O(1) amortized!10. Sigma Notation
Sigma notation (Σ) is shorthand for "add up a bunch of terms." If you can read a for loop, you can read sigma notation -- they're the same thing.
Σi=startend f(i) = f(start) + f(start+1) + ... + f(end)
Read it as: "Sum of f(i), for i going from start to end"
# MATH: Σᵢ₌₁ⁿ f(i)
# CODE:
total = 0
for i in range(1, n+1): # i = start to end
total += f(i) # body = the expression after Σ
#
# Bottom of Σ → loop start (i=1)
# Top of Σ → loop end (n)
# Expression after Σ → loop body (f(i))
# Σ itself → the += accumulatorEvery time you see Σ, mentally translate it to a for loop. Every time you see a for loop accumulating a total, mentally translate it to Σ.
Σi=15 i = 1 + 2 + 3 + 4 + 5 = 15
Σi=14 i² = 1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30
Σi=03 2i = 20 + 21 + 2² + 2³ = 1 + 2 + 4 + 8 = 15
Σi=1n i = 1 + 2 + 3 + ... + n = n(n+1)/2
Σi=0n-1 2i = 1 + 2 + 4 + ... + 2(n-1) = 2n - 1
# This Python loop:
total = 0
for i in range(1, n+1):
total += i * i
# Is equivalent to: Σᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6# This loop:
total = 0
for i in range(n):
for j in range(i):
total += 1
# Total iterations: Σᵢ₌₀ⁿ⁻¹ i = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2Useful Sigma Properties
| Property | Meaning |
|---|---|
| Σ (f + g) = Σ f + Σ g | Sum of sums = sum each separately |
| Σ c×f = c × Σ f | Constants can be pulled out |
| Σi=1n c = c×n | Sum of a constant n times = c×n |
11. Key Sum Formulas for CS
These formulas appear constantly in algorithm analysis. Understand them, and Big-O proofs become easy.
| Sum | Formula | Big-O | Where It Appears |
|---|---|---|---|
| 1 + 2 + 3 + ... + n | n(n+1)/2 | O(n²) | Selection sort, bubble sort, triangular nested loops |
| 1² + 2² + 3² + ... + n² | n(n+1)(2n+1)/6 | O(n³) | Some triple-nested patterns, matrix operations |
| 1³ + 2³ + 3³ + ... + n³ | [n(n+1)/2]² | O(n4) | Rare, but good to know |
| 1 + 2 + 4 + ... + 2(n-1) | 2n - 1 | O(2n) | Binary trees, recursive branching, naive Fibonacci |
| 1 + r + r² + ... + rn | (r(n+1) - 1)/(r - 1) | O(rn) | General geometric growth |
| n + n/2 + n/4 + ... + 1 | ≈ 2n | O(n) | Merge sort total work, build-heap |
| 1 + 1/2 + 1/3 + ... + 1/n | ≈ ln(n) + 0.577 | O(log n) | QuickSort average, coupon collector |
When analyzing an algorithm:
- Count what the loop does at each iteration
- Write the total as a sum
- Match it to one of these formulas
- Read off the Big-O
Example: Inner loop does n, n-1, n-2, ..., 1 work → that's row 1 → n(n+1)/2 → O(n²)
This seems like it should be large because there are log(n) terms. But the sum is only about 2n!
n + n/2 + n/4 + n/8 + ... = n(1 + 1/2 + 1/4 + 1/8 + ...) = n × 2 = 2n
The key: each term is HALF the previous, so later terms contribute almost nothing.
This is why building a heap is O(n), not O(n log n)! The work at each level halves as you go up.
12. Harmonic Series
The harmonic series is special -- it grows, but very slowly:
The 0.5772... is the Euler-Mascheroni constant (γ). For Big-O, we just say Hn = O(log n).
| n | Hn (approx) |
|---|---|
| 1 | 1.000 |
| 10 | 2.929 |
| 100 | 5.187 |
| 1,000 | 7.485 |
| 1,000,000 | 14.357 |
| 1,000,000,000 | 21.300 |
After a billion terms, the sum is only about 21. That's incredibly slow growth!
"How many random draws do you need to collect all n distinct items?"
Expected draws = n × Hn ≈ n × ln(n)
With 100 possible items, you'll need about 100 × ln(100) ≈ 100 × 4.6 ≈ 460 draws on average to see them all. The harmonic series tells you why: after getting 50/100 items, half your draws are "wasted" on duplicates, and it gets worse as you approach completion.
13. Recursive Sequences
Some sequences define each term using previous terms instead of a direct formula. These are recurrence relations -- and they're central to algorithm analysis.
The Fibonacci Sequence
F(n) = F(n-1) + F(n-2) for n ≥ 2
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
| n | F(n) | How |
|---|---|---|
| 0 | 0 | Base case |
| 1 | 1 | Base case |
| 2 | 1 | F(1) + F(0) = 1 + 0 |
| 3 | 2 | F(2) + F(1) = 1 + 1 |
| 4 | 3 | F(3) + F(2) = 2 + 1 |
| 5 | 5 | F(4) + F(3) = 3 + 2 |
| 6 | 8 | F(5) + F(4) = 5 + 3 |
| 7 | 13 | F(6) + F(5) = 8 + 5 |
Each call branches into two more calls:
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2) # Two recursive calls!The number of calls forms a geometric-like growth: roughly 2n. This is because each level of the recursion tree has (up to) twice as many calls as the level above -- a geometric sequence!
Fix: Use DP (memoization) to avoid recomputation → O(n).
Recurrence Relations in Algorithms
| Algorithm | Recurrence | Solution |
|---|---|---|
| Binary Search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge Sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Naive Fibonacci | T(n) = T(n-1) + T(n-2) + O(1) | O(2n) |
| Linear scan | T(n) = T(n-1) + O(1) | O(n) |
Each recurrence defines a recursive sequence where T(n) is the time complexity for input size n.
The Master Theorem provides formulas to solve recurrences of the form T(n) = aT(n/b) + O(nd). It's covered in depth on the Discrete Math page, but the key idea is: it tells you which term "wins" -- the recursive splitting or the work at each level. This is all based on comparing geometric series!
14. Real-World Applications
| Concept | Type | Application |
|---|---|---|
| Loop iteration counting | Arithmetic series | n(n+1)/2 → O(n²) for nested loops |
| Binary tree structure | Geometric series | 2n - 1 total nodes |
| Recursive branching | Geometric sequence | 2n calls → O(2n) |
| Binary search halving | Geometric decay | n, n/2, n/4, ... → O(log n) steps |
| Dynamic array resizing | Geometric series | 1 + 2 + 4 + ... + n ≈ 2n → O(1) amortized |
| Memory addressing | Arithmetic sequence | Base + index × size → O(1) array access |
| Merge sort work | Geometric series | n work per level × log n levels → O(n log n) |
| Bit representations | Geometric series | n bits represent 2n values (0 to 2n - 1) |
| Compound interest | Geometric sequence | Principal × (1 + rate)n |
| Build-heap operation | Geometric series | n + n/2 + n/4 + ... = O(n), not O(n log n) |
Arithmetic series (adding same amount) = polynomial growth = usually O(n²)
Geometric series with r > 1 (multiplying) = exponential growth = usually O(2n) or O(rn)
Geometric series with r < 1 (dividing) = converges = often O(n) amortized
Harmonic series (1/i terms) = logarithmic growth = O(log n)
Recognizing which type of series you're dealing with instantly tells you the Big-O class.
15. Practice Quiz
Test your understanding of sequences and series. Click an answer to check it.
1. What is the 20th term of the arithmetic sequence 5, 9, 13, 17, ...?
a1 = 5, d = 4. Using an = a1 + (n-1)d: a20 = 5 + (20-1)(4) = 5 + 76 = 81.
2. What is 1 + 2 + 3 + ... + 50?
Using n(n+1)/2: 50(51)/2 = 2,550/2 = 1,275.
3. A loop runs n + (n-1) + (n-2) + ... + 1 iterations total. What is its time complexity?
This is an arithmetic series: n + (n-1) + ... + 1 = n(n+1)/2. Expanding: n²/2 + n/2. Dropping constants and lower terms: O(n²).
4. What is the 6th term of the geometric sequence 3, 6, 12, 24, ...?
a1 = 3, r = 2. Using an = a1 × r(n-1): a6 = 3 × 25 = 3 × 32 = 96.
5. What is 1 + 2 + 4 + 8 + 16 + 32 + 64?
This is a geometric series with a1 = 1, r = 2, n = 7 terms. Sum = 27 - 1 = 128 - 1 = 127.
6. What does the infinite sum 1 + 1/3 + 1/9 + 1/27 + ... converge to?
a1 = 1, r = 1/3. Since |r| < 1, S∞ = a1/(1-r) = 1/(1 - 1/3) = 1/(2/3) = 3/2.
7. A complete binary tree of height 5 has how many total nodes?
Total nodes = 1 + 2 + 4 + 8 + 16 + 32 = 26 - 1 = 63. This is the geometric series sum with 6 levels (height 5 means levels 0 through 5).
8. The sum n + n/2 + n/4 + n/8 + ... + 1 is approximately:
Factor out n: n(1 + 1/2 + 1/4 + 1/8 + ...). The part in parentheses is a convergent geometric series with r = 1/2, summing to 1/(1 - 1/2) = 2. So the total is n × 2 = 2n. This is why build-heap is O(n)!