Brute-force three-sum
Three nested loops, each starting after the one outside it, so every combination of three distinct positions is examined exactly once and none is examined twice. That is n choose 3, which is n(n−1)(n−2)/6 — a cubic. The input here is a permutation of 1 to n, so no triple ever sums to zero and the loops never stop early: what is measured is exactly the number of triples rather than how lucky the shuffle was.
The claim being tested
O(n³)
When it is the right choice
The brute force is worth writing once, to have something correct to check a better algorithm against. It is not worth running: the standard improvement sorts the list and then, for each element, walks two pointers inwards, which is O(n²) and beats this by a factor of n. That factor is what this page is for — at n = 512 the cubic examines 22,238,720 triples where the quadratic would do about 130,000.
How it works
- Loop over every position i.
- Loop over every position j after i.
- Loop over every position k after j.
- Count the triple, and check whether the three numbers add to zero.
Worth noticing
- The measured gradient is 3.09, and having roughly 1, 2 and 3 on the same pair of axes — linear search, selection sort, this — is what makes the log-log gradient readable as an exponent rather than believable as one.
- This is the steepest polynomial in the catalogue and the smallest ceiling: 512, where the sorts reach 4,096 and the linear subjects 131,072. Seven measured sizes rather than fifteen, because a cubic runs out of budget three decades sooner, and a fit over seven points is weaker evidence than a fit over fifteen. Said plainly rather than hidden in the fit.
- Doubling n multiplies the count by about 8, and it approaches 8 from above as n grows: the step to 16 multiplies it by 10.0 and the step to 512 by 8.05. The −1 and the −2 in n(n−1)(n−2) are worth something at small n, which is a good reminder that an asymptotic claim is a claim about large n — and it is why the measured gradient is 3.09 rather than 3.00.
Cost
- Best
- O(n³)
- Average
- O(n³)
- Worst
- O(n³)
- Extra space
- O(1)
- n is
- the length of a list of numbers
- Measures
- shuffled: up to n = 512; sorted: up to n = 512; reversed: up to n = 512
The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.
A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.