Maximum subarray: a controlled empirical study (1D and 2D)

How Much Does the Algorithm Matter? A Controlled Empirical Study of the Maximum Subarray Problem, from O(n³) to O(n), in One and Two Dimensions Paul Christopher Aimé · ENSA Marrakech, Cadi Ayyad University · March 2025

A study with verified implementations, exact operation counts, repeated and calibrated timings, bootstrap confidence intervals and model selection.

• Paper: paper/paper.pdf · Poster (A0): poster/poster.pdf
• Every number in the paper is in results/summary.json; raw timings are the CSV files in results/.

Headline results (g++ 13.3, -O2, one core of a 2.1 GHz Xeon VM)

Algorithm (1D)	Fitted log–log slope [95% CI]	Theory	Best-fitting law
Naive	2.95 [2.92, 2.995]	3	n³
Running sums	2.01 [1.99, 2.01]	2	n²
Divide & conquer	1.08 [1.06, 1.08]	1 + log	n log n
Kadane	1.000 [0.998, 1.002]	1	n

• Kadane is 304× faster than running sums at n = 2¹⁰ and ~20 000× at n = 2¹⁶; 8–16× faster than divide & conquer.
• 740 091 correctness checks pass; 140/140 exact operation counts match closed forms.
• A tuned hybrid D&C (cutoff 8) gains only 1.2–1.4×; compilers change constants up to 17×, not exponents.
• 2D: compress over pairs of the shorter side (up to 2 741× faster on a 4×16384 matrix); row-pair compression beats column pairs by 3.1× at N = 1024; the 2D D&C is 6.5–7.9× slower than Kadane compression.

Pipeline

flowchart LR
  A[include/msub.hpp<br/>5 x 1D + 5 x 2D algorithms] --> T[tests/test_correctness.cpp<br/>740k checks vs. naive oracle]
  A --> O[src/opcount.cpp<br/>exact counts vs. closed forms]
  A --> B[src/bench.cpp<br/>calibrated, interleaved timing]
  B --> R[(results/*.csv)]
  O --> R
  R --> AN[analysis/analyze.py<br/>slopes, bootstrap CI, model selection]
  AN --> S[results/summary.json]
  AN --> F[figures/*.pdf]
  S --> TB[analysis/make_tables.py]
  TB --> P[paper/paper.pdf]
  F --> P
  F --> PO[poster/poster.pdf]

Loading

Layout

include/msub.hpp          algorithms (header-only, C++17), optional exact operation counters
tests/test_correctness.cpp differential + property tests
src/opcount.cpp           counted additions vs. closed forms  -> results/opcount.csv
src/bench.cpp             timing harness (1d | 2d | rect modes)
run_experiments.sh        reruns every experiment (~15 min, one core)
analysis/                 analyze.py, make_tables.py, illustrations.py, style.py
results/                  raw CSVs, summary.json, test and run logs
figures/  paper/  poster/ outputs

Reproduce

./run_experiments.sh                 # tests, op counts, all timing experiments
python analysis/analyze.py           # slopes, CIs, figures, results/summary.json
python analysis/illustrations.py
python analysis/make_tables.py
make paper poster                    # needs a LaTeX installation with tikzposter

Run on an otherwise idle machine; absolute times depend on hardware, exponents and ratios should not. Python needs numpy, pandas, matplotlib.

Conventions

The subarray is non-empty (all-negative input → largest single element). Values are int32, sums int64.

Licence

See LICENSE.