Part I · Analysis of algorithms · week 1

3-sum (brute force)

Count triples summing to zero by trying all of them. The point is not the algorithm: it is watching a cubic loop and learning to predict its cost.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

time	~n³/6
doubling ratio	8× per 2× input
space	O(1)
better	n² lg n by sorting

Reference: Sedgewick & Wayne, §1.4.

3-sum (brute force) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def count_triples(a):
    # Brute force: every unordered triple i < j < k is tried once, so the
    # loop body runs n(n-1)(n-2)/6 times -- that is ~n^3/6.
    n = len(a)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[i] + a[j] + a[k] == 0:
                    count += 1
    return count

Why it works

Reading the cost off the code

Three nested loops over the same array, each starting one past the last: the body runs C(n,3) = n(n−1)(n−2)/6 times. Discard the low-order terms and you get ~n³/6. The tilde notation exists precisely so you can say that without pretending to know the constant factor of a machine instruction.

The doubling hypothesis

Instead of counting operations, measure: time n, then 2n, then 4n. If each doubling multiplies the time by about 8, the running time is ~a n³ because 2^b = 8 gives b = 3. This is the course's practical method for finding an exponent without reading a single line of code — and it is how you check that your predicted order of growth is the real one.

Doing better

Sort the array, then for every pair (i, j) binary-search for -(a[i] + a[j]): n² lg n. Better still, walk two pointers inwards for a linear scan per i: n². On 8,000 numbers that is the difference between minutes and milliseconds — and no lower bound below n² is known, which is itself a fact worth knowing.

What to try in the animation

Every triple is checked. 8 numbers means 56 checks; 16 would mean 560. That ratio — 8× the work for 2× the input — is the signature of a cubic algorithm.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

course example — 30 -40 -20 -10 40 0 10 5
no solutions — 1 2 3 4 5 6 7
many solutions — -3 -2 -1 0 1 2 3

Open 3-sum (brute force) in the player →

The rest of Analysis of algorithms

Binary search Halve the interval that could still contain the key.