Schreier–Sims algorithm

The Schreier-Sims algorithm is an efficient method of computing a strong generating set (SGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS is critical for many algorithms in computational group theory,computer algebra systems typically rely on the Schreier-Sims algorithm for efficient calculations in groups.

The running time of Schreier-Sims varies on the implementation. Let $G\leq S_{n}$ be given by $t$ generators. For the deterministic version of the algorithm, possible running times are:

• $O(n^{2}\log ^{3}|G|+tn\log |G|)$ requiring memory $O(n^{2}\log |G|+tn)$
• $O(n^{3}\log ^{3}|G|+tn^{2}\log |G|)$ requiring memory $O(n\log ^{2}|G|+tn)$

For Monte Carlo variations of the Schreier-Sims algorithm, we have the following estimated complexity:

• $O(n\log n\log ^{4}|G|+tn\log |G|)$ requiring memory $O(n\log |G|+tn)$

In computer algebra systems, an optimized Monte-Carlo algorithm is typically used.