Arithmetic vs Geometric Series: The Two Sums Behind Big-O

You've seen someone in an interview just... write down O(n log n) without blinking. No pause, no hesitation. Just the answer. Meanwhile you're staring at the same recursive function trying to remember whether this is the Master Theorem case where a > b^d or where b^d > a, and honestly at this point you'd accept either one.

Almost every Big-O bound reduces to a sum, and two series patterns account for nearly all of them: arithmetic and geometric. Recognize which one you're looking at and you can derive most time complexity results from scratch instead of from memory.

The Arithmetic Series: Adding Up a Triangle

An arithmetic series has a constant difference between consecutive terms. The most common version in code: 1 + 2 + 3 + ... + n.

1 + 2 + 3 + ... + n = n(n+1)/2

That's O(n²). The clean way to see it without memorizing anything: write the sequence forward and backward, then pair up terms.

1    +  2    +  3    + ... + n
n    + (n-1) + (n-2) + ... + 1
----
(n+1) (n+1) (n+1)      (n+1)  ← n pairs

Total = n(n+1)/2. The sum of the first n integers is always O(n²).

Gauss allegedly figured this out at age 10 to dodge adding up 100 numbers by hand. You can use the same trick to dodge memorizing Big-O bounds. If Gauss could do it at 10, you can do it during a 45-minute interview.

Where You See This in Code

The trigger: a nested loop where the inner loop's range depends on the outer index.

def count_pairs(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):  # inner loop shrinks each iteration
            count += 1
    return count

When i=0 the inner loop runs n-1 times. When i=1, it runs n-2 times. Down to 0. Total = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²).

Insertion sort, bubble sort, naive 3Sum. All the same triangle. If you draw which (i, j) pairs get visited, you get the lower half of a grid. The shape is always a triangle.

Drake meme disapproving clean nested for loops, approving an obfuscated single-loop hack using modular arithmetic

Flattening the nested loop doesn't change the math. The triangle follows you.

Arithmetic series show up in space too. Storing all pairs from n elements gives n(n-1)/2 entries: O(n²). An adjacency matrix for a complete graph is the same sum underneath.

The Geometric Series: Doubling (or Halving)

A geometric series has a constant ratio between consecutive terms.

a + ar + ar² + ar³ + ... + ar^(k-1) = a × (r^k - 1) / (r - 1)

Two flavors matter in interviews. They behave in opposite directions and it's mildly counterintuitive which one collapses nicely.

When r > 1: The Last Term Dominates

1 + 2 + 4 + 8 + ... + 2^(k-1) = 2^k - 1

The last term is 2^(k-1). The entire sum is 2^k - 1, just under twice the last term. In a geometric series with r > 1, the last term alone determines the order of the sum. All the earlier terms combined don't even equal the last one.

This is why a complete binary tree with n leaves has about 2n - 1 total nodes. Level 0 has 1 node, level 1 has 2, up through log n levels to n leaves. Total = 1 + 2 + 4 + ... + n = 2n - 1 = O(n). Every non-leaf level combined has fewer nodes than the leaf level alone.

When r < 1: The First Term Dominates

n + n/2 + n/4 + n/8 + ... = n × (1 / (1 - 1/2)) = 2n

In a geometric series with r < 1, the first term dominates and the total is at most twice that first term. This is the opposite regime: all the later terms shrink fast enough that they barely add anything.

The canonical example is dynamic array resizing. Each resize copies all current elements. Start at size 1 and double repeatedly to reach size n:

Total copies = n + n/2 + n/4 + ... + 2 + 1
             = n × (1 + 1/2 + 1/4 + ...) 
             = 2n
             = O(n)

This is why append() on a Python list is amortized O(1). Individual resizes copy O(n) elements. But the total across all n appends is O(n). Divide by n appends: O(1) each on average. The expensive resize gets amortized over everything that led up to it.

Recursion Trees Are Just Geometric Series in Disguise

This is where the two series types directly determine which Master Theorem case applies.

Take T(n) = 2T(n/2) + f(n). Each level of the recursion tree does some work across all its nodes. Add up the work across every level and you get a series. The question is: does that series grow, stay flat, or shrink as you go deeper?

If you don't understand recursion, read this meme again.

The geometric series with r > 1 and no base case.

Case 1: Work per level decreasing (r < 1). If f(n) = n²:

Level 0: 1 subproblem × n²      = n²
Level 1: 2 subproblems × (n/2)² = n²/2
Level 2: 4 subproblems × (n/4)² = n²/4

Each level halves. The series converges to about 2n². The top level dominates. O(n²).

Case 2: Work per level constant. If f(n) = n:

Level 0: 1 × n      = n
Level 1: 2 × (n/2)  = n
Level 2: 4 × (n/4)  = n

Every level does exactly n work across log n levels. Total: n log n. This is merge sort.

Case 3: Work per level increasing (r > 1). If f(n) = 1 (constant work per call):

Level 0:     1 × 1 = 1
Level 1:     2 × 1 = 2
Level 2:     4 × 1 = 4
Level log n: n × 1 = n

Each level doubles. The leaf level dominates. Total ≈ 2n. O(n).

Three side-by-side bar charts showing recursion tree work per level: decreasing bars (Case 1), equal bars (Case 2), and increasing bars (Case 3)

The Master Theorem is a named result for these three series behaviors. Know what it's actually asking and you stop needing to memorize which case is which. Case 1 = geometric r < 1 (top dominates). Case 2 = flat. Case 3 = geometric r > 1 (bottom dominates).

Every Common Pattern in One Table

Pattern	Series	Sum
Triangular nested loop	1 + 2 + ... + n	O(n²)
Binary recursion, constant work/call	1 + 2 + 4 + ... + n	O(n)
Binary recursion, O(n) work/call	n + n + n + ... (log n times)	O(n log n)
Work halving each level	n + n/2 + n/4 + ...	O(n), first term dominates
Dynamic array resizing	n + n/2 + n/4 + ...	O(n) total, O(1) amortized
Complete binary tree nodes	1 + 2 + 4 + ... + n	O(n)
All subsets of n elements	2⁰ + 2¹ + ... + 2^n	O(2^n)

Arithmetic or Geometric: How to Tell

Look at consecutive terms. Constant difference? Arithmetic. Constant ratio? Geometric.

In code: does the inner loop size grow additively with the outer index? Arithmetic. Does each level of recursion multiply the number of subproblems? Geometric.

# Arithmetic: inner loop grows by 1 each outer iteration
for i in range(n):
    for j in range(i):   # 0, 1, 2, ..., n-1 iterations
        pass             # total: O(n²)

# Geometric: each level spawns 2× as many calls
def count(n):
    if n == 0: return 0
    return count(n - 1) + count(n - 1)  # 1, 2, 4, ..., 2^n calls

It's a two-second check once you know what to look for. The difference between a triangle and an exponential is not subtle.

Walking through the summation in a live interview builds far more credibility than reciting a memorized result. It shows you understand where the bound comes from, not just what it is. If you want to practice this kind of live derivation, SpaceComplexity runs voice-based mock interviews where you explain your reasoning out loud in real time, not just type code.

What About Partial Series?

Sometimes a recursion tree doesn't run all the way to n, you cut off early once subproblems are small enough. For r > 1, the last term still dominates even in a partial series, so the bound barely changes. For r < 1, cutting off early only makes the sum smaller. Constant thresholds rarely change the asymptotic answer.

The Harmonic Series Gives O(n log n)

The harmonic series 1 + 1/2 + 1/3 + ... + 1/n ≈ ln(n) = O(log n) shows up less often but is worth knowing. Multiply each term by n and you get O(n log n). This is where quicksort's average-case analysis comes from: expected comparisons are roughly 2n ln n, because each element gets compared against an approximately uniform random partition. The harmonic series is where the log factor hides in algorithms that aren't obviously divide-and-conquer.