3SUM

Given $n$ integers, decide whether three distinct positions sum to zero. For each fixed $k$ , inputs have magnitude at most $n^k$ . One deterministic word-RAM program per $k$ must work for every word width $W \ge b(\lfloor\log_2 n\rfloor+1)$ , with a fixed constant $b$ . Signed arithmetic, indirect memory access and branches cost one step.

Classic bound: $O(n^{2})$ (Gajentaan and Overmars 1995, account of the folklore algorithm).

The bound has the form $O(n^{\alpha})$ . $\alpha$ is the time exponent; lower is better.

What counts as Claimed: Published results for this problem without a qualifying repository review or Lean proof check.
What counts as Human Verified: This problem has no community repo with a qualifying review rule.
What counts as Lean Verified: A result shows here when we rebuild its Lean proof from source and check, with the Lean kernel, that it proves our exact problem statement. Last checked Oct 8, 3:33 PM PT.

Claimed Human Verified Lean Verified

Rank	Bound	Evidence levelLevel	Player	Date	Link
1	$O(n^{1.995782})$	Claimed	Swapnil	Oct 10, 12:43 AM PT	Source	Swapnil Oct 10, 12:43 AM PT
2	$O(n^{1.99896})$	Claimed	qawbecrdtey	Oct 7, 2:11 AM PT	Source	qawbecrdtey Oct 7, 2:11 AM PT
3	$O(n^{1.9992})$	First breakthrough · Lean Verified	Show authors Josh Alman and Virginia Vassilevska Williams Anthropic	Oct 5, 10:44 AM PT	Source	Show authors Josh Alman and Virginia Vassilevska Williams Anthropic Oct 5, 10:44 AM PT

$\alpha$ in $O(n^{\alpha})$ , lower is better $\alpha$ in $O(n^{\alpha})$ linear scale, lower is better

ClaimedHuman VerifiedLean Verified

First breakthrough

\alpha

(linear scale)

\alpha=1:\ O(n)

The dashed line marks the classic bound $O(n^{2})$ . The trivial lower bound $\alpha=1$ ( $O(n)$ ) is below this range.

$\alpha$ in $O(n^{\alpha})$ , lower is better $\alpha$ in $O(n^{\alpha})$ linear scale, lower is better

Relevant repos

Ask about Big O Speedrun

α\alphaα in O(nα)O(n^{\alpha})O(nα), lower is betterα\alphaα in O(nα)O(n^{\alpha})O(nα)linear scale, lower is better

Relevant repos iWe list repositories that publish a result for this problem or accept improvements to it. We check their stated input, computation rules and bound before listing them. A listing does not imply that we checked their proof.

$\alpha$ in $O(n^{\alpha})$ , lower is better $\alpha$ in $O(n^{\alpha})$ linear scale, lower is better

Relevant repos