computational-complexity-validation

computational-complexity-validation

Summary

Empirically validate theoretical time and space complexity claims of a scalable algorithm by executing it on progressively large datasets (10M+ cells), measuring wall-clock runtime and peak memory, and plotting observed metrics against the predicted complexity curve to confirm linear or sublinear behavior.

When to use

When an algorithm claims linear or sublinear time/space complexity (e.g., matrix-free spectral embedding) and you need to verify that claim holds for datasets at the scale intended (10 million+ cells). Typical trigger: the algorithm's documentation or paper asserts O(n) or O(n log n) complexity, but you have access to datasets large enough to test empirically, and the scaling behavior is critical to your application's feasibility.

When NOT to use

• Algorithm documentation does not make an explicit complexity claim to validate.
• Datasets available are too small (< 100K cells) to reliably distinguish linear from polynomial growth; noise in measurements dominates.
• Input is already preprocessed to a lower-dimensional representation (e.g., PCA scores, gene expression matrix); complexity validation requires full-rank or near-full-rank input.

Inputs

• single-cell count matrix in CSR (compressed sparse row) format with ≥1M cells
• cell and feature annotation metadata (optional but recommended for reproducibility)

Outputs

• wall-clock runtime measurements (seconds) for each dataset size
• peak memory usage (GB) for each dataset size
• log-log plot of runtime vs. cell count with fitted complexity slope
• log-log plot of memory vs. cell count with fitted complexity slope
• summary table: cell count, runtime, peak memory, eigenvectors returned, output structure validation status

How to apply

Execute the algorithm on a series of datasets of increasing size (e.g., 1M, 5M, 10M+ cells), ensuring input matrices are in the same sparse format (e.g., CSR) that the algorithm expects. Measure wall-clock runtime using Python's time module or system profilers, and track peak memory consumption throughout execution using memory_profiler or psutil. Record the number of output features (e.g., eigenvectors) and verify they match expected output structure (e.g., weighted by eigenvalues). Plot runtime and memory against dataset size on log-log axes; a linear complexity algorithm should produce a slope near 1.0 when both axes are logarithmic. Analyze deviations from theory—actual overhead, constant factors, and memory alignment effects often cause a steeper slope at smaller sizes—and document whether the observed complexity is consistent with the published claim at the target scale.