Every run picks n candidate biomarker genes (each with a random expression-deviation weight) and a diagnostic target sum, then times four real algorithms on the same systems-biology dataset with performance.now() — nothing here is a formula guess, every bar is a measured wall-clock duration.
verify one panel: O(n) — sum n weights, compare to target
sort expression set: O(m log m) — m = n·3000 "genome-wide" values
pairwise correlation: O(k²) — k = n·35 candidates, all gene pairs
find the panel: O(n·2ⁿ) — try every one of 2ⁿ subsets
The brute-force row is a real subset-sum search: for each of the 2ⁿ subsets of the shortlist it sums the included genes and checks the target — the textbook NP-hard combinatorial-search pattern behind picking a minimal biomarker panel, choosing a gene set for a network hub, or any "does some combination explain the phenotype" question in systems biology. Verifying one proposed panel is cheap and linear; finding it by exhaustion is not.
- Shortlist size n — candidate genes fed to the exhaustive subset search; doubling n doubles the subset count, so the exponential bar can leap off the chart while the others barely move.
- Run benchmark — executes all four algorithms live at the current n and appends one new column of bars to the skyline.
- Y-axis scale — log makes small polynomial bars visible next to a huge exponential one; linear shows the raw disparity in real proportion.
Equations. Subset-sum: find S ⊆ {1..n} with Σi∈S wi = T. Exhaustive cost = n·2ⁿ additions (the inner loop adds up to n weights per subset; the benchmark counts 2ⁿ subsets exactly). Meet-in-the-middle splits the panel into halves and matches sums of one half against T minus sums of the other: cost O(2n/2) time and memory, so it still grows exponentially, only with the square-root base √2 ≈ 1.41 per gene instead of 2.
Honest simplifications. Weights are synthetic integers, not real expression data, and subset-sum is only a stand-in for panel selection (real pipelines optimise classification accuracy, not an exact sum). Timings are single-thread JavaScript wall-clock values: they vary with the CPU, JIT warm-up and browser timer resolution, so tiny bars are noisy; the 2ⁿ subset counts are exact. The independent check compares two different algorithms on identical weights and must return the same number of matching panels.
Real-world relevance: this is why genomics pipelines never brute-force a full gene panel — they use the fast O(n)/O(n log n)/O(n²) stages to shortlist candidates first, and only run exhaustive or heuristic search over the small remainder, exactly as staged here.