Computational complexity and run-time comparison.

The table lists the theoretical complexity and run-time (in seconds) of the four methods, SMASH, SPARK-X, SpaGene, and SpatialDE in a simulation setup with K = 1000 genes and varying number of cells N. The number of spatial coordinates d was equal to 2. *SpaGene constructs multiple kNN graphs and performs permutation tests. We are only listing the complexity of the KNN algorithm.