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 ( 1.0 (e.g., 1.5–2.0) indicates sublinear scaling relative to claim.
• Peak memory vs. cell count plot exhibits slope ≈ 1.0 on log-log axes (confirming linear space complexity); slope significantly > 1.0 suggests memory scaling is worse than linear.
• Measured peak memory is within the theoretical CSR matrix overhead (nnz 2 8 bytes for data + colindices, plus rowpointers and auxiliary structures), not orders of magnitude higher.
• Output eigenvectors are present, correctly weighted by eigenvalues, and their count matches expected behavior (e.g., default 30 in Release 2.3.0) across all tested dataset sizes.
• Runtime and memory measurements show consistent, monotonic growth with dataset size; random fluctuations are small relative to the trend (coefficient of variation < 20% across replicates if available).

Limitations

• Empirical validation is sensitive to hardware (CPU cache, memory architecture, I/O speed), competing processes, and data layout; results may not generalize across different compute environments.
• Constant factors and overhead dominate at small dataset sizes (< 1M cells), making it difficult to distinguish linear from polynomial complexity without very large datasets; 10M+ cell experiments are computationally expensive.
• Memory measurement captures peak usage at a point in time; some algorithms may have multiple phases with different memory footprints, and a single peak snapshot may not capture the true worst-case.
• Similarity metric choice (cosine, Euclidean, etc.) can affect both runtime and memory; the article specifies cosine as default in Release 2.3.0, but other metrics may show different scaling properties.
• Sparse matrix fill rate and feature diversity affect practical runtime independent of theoretical complexity; two 10M-cell matrices with different sparsity patterns will show different execution times even if complexity class is identical.

Evidence

• [other] Does the matrix-free spectral embedding algorithm (tl.spectral) in SnapATAC2 achieve linear time and space complexity when applied to datasets of 10 million or more cells?: "Does the matrix-free spectral embedding algorithm (tl.spectral) in SnapATAC2 achieve linear time and space complexity when applied to datasets of 10 million or more cells?"
• [other] SnapATAC2 is capable of scaling to more than 10 million cells, demonstrating its capacity to handle very large single-cell datasets.: "SnapATAC2 is capable of scaling to more than 10 million cells, demonstrating its capacity to handle very large single-cell datasets."
• [other] Execute tl.spectral with cosine similarity metric (the default similarity metric as of Release 2.3.0) and capture wall-clock runtime using Python's time module or system profiler.: "Execute tl.spectral with cosine similarity metric (the default similarity metric as of Release 2.3.0) and capture wall-clock runtime using Python's time module or system profiler."
• [other] Monitor and record peak memory usage throughout the spectral decomposition using a memory profiler (e.g., memoryprofiler or psutil).: "Monitor and record peak memory usage throughout the spectral decomposition using a memory profiler (e.g., memoryprofiler or psutil)."
• [other] Analyze runtime and peak memory against the reported linear complexity claim by plotting execution metrics.: "Analyze runtime and peak memory against the reported linear complexity claim by plotting execution metrics."
• [intro] Scale to more than 10 million cells.: "Scale to more than 10 million cells."
• [intro] Matrix-free spectral embedding algorithm that is applicable to a wide range of single-cell omics data, including single-cell ATAC-seq, single-cell RNA-seq, single-cell Hi-C, and single-cell: "Matrix-free spectral embedding algorithm that is applicable to a wide range of single-cell omics data"

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: HolobiomicsLab
• Source: HolobiomicsLab/asb-skill-collections
• License: Apache-2.0
• Homepage: https://holobiomicslab.cnrs.fr

Install and usage instructions live in the source repository linked above.