Space and time complexities for network-based (SSA) and network-free (NF) stochastic simulation algorithms.

aNo dependency graph.bDependency graph [37], [38].cLogarithmic classes (with dependency graph) [21], [39], [40].dNext-reaction method (with dependency graph) [37].eDirect method (with or without dependency graph) [20].fPolymerizing systems in gel phase [23], [42] (see Fig. 5B).gDirect method-like implementation.Scalings are shown with respect to particle number, , and number of reactions, , or rules, . For combinatorially-complex models, . Note that time complexity is given on a “per event” (reaction/rule firing) basis. If a reaction dependency graph [37] is used, the space and time complexities of SSA methods with respect to depend on , the maximum number of reactions updated after each reaction firing [37], [38]. In combinatorially-complex models, often increases with (see Figure S1 of the supporting information). The time complexity of SSA methods with respect to also depends on the method used for selecting the next reaction to fire in the system. Scalings are shown for three different SSA variants that use different selection methods [20], [21], [37], [39], [40]. Also note that optimized variants of the direct method [21], [38], [41] have been shown to outperform methods with lower asymptotic complexity in some cases [38]. Space and time complexities of the NF algorithm with respect to assume no dependency graph and that the next rule to fire is selected as in Gillespie's direct method [20], although in principle other variants are possible.