Editing Schreier–Sims algorithm (section)

== Background and timing ==

The algorithm is an efficient method of computing a [[base (group theory)|base]] and [[strong generating set]] (BSGS) 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 system]]s typically rely on the Schreier–Sims algorithm for efficient calculations in groups.

The running time of Schreier–Sims varies on the implementation.  Let <math> G \leq S_n </math> be given by <math>t</math> [[Generating set of a group|generators]].  For the [[deterministic]] version of the algorithm, possible running times are:

* <math>O(n^2 \log^3 |G| + tn \log |G|) </math> requiring memory <math>O(n^2 \log |G| + tn)</math>
* <math>O(n^3 \log^3 |G| + tn^2 \log |G|) </math> requiring memory <math>O(n \log^2 |G| + tn) </math>

The use of [[Schreier vector]]s can have a significant influence on the performance of implementations of the Schreier–Sims algorithm.

The [[Monte Carlo algorithm|Monte Carlo]] variations of the Schreier–Sims algorithm have the estimated complexity:

: <math>O(n \log n \log^4 |G| + tn \log |G|)</math> requiring memory <math>O(n \log |G| + tn)</math>.

Modern computer algebra systems, such as [[GAP computer algebra system|GAP]] and [[Magma computer algebra system|Magma]], typically use an optimized [[Monte Carlo algorithm]].