35.9. Limits on time and space🔗

Many operations have a second form that takes a limit, and the end of its name says what kind of limit it is.

A name ending in Capped means that the limit is on the size of the output. Hex.PermGroup.Group.elementsCapped lists the elements of a group. It compares the limit with the order of the group before doing any other work, and when the order is larger it returns an error carrying the order. Hex.PermGroup.Group.leftCosetsCapped does the same with the index, and Hex.PermGroup.Group.blockAction takes a limit of this kind on the number of blocks. Hex.PermGroup.Group.derivedSeriesCapped computes at most the given number of terms of the derived series and returns the terms it computed.

A name ending in Budgeted means that the operation counts its work as it goes and stops when a budget runs out. Hex.PermGroup.Group.buildBudgeted is the budgeted form of Hex.PermGroup.Group.ofGenerators: it returns the same group when the budget suffices, and otherwise reports which resource ran out, with no group. Some budgeted operations return what they have found so far. Hex.PermGroup.Group.centralizerBudgeted, Hex.PermGroup.Group.normalizerBudgeted and Hex.PermGroup.Group.setStabilizerBudgeted return either the answer or a subgroup of it. Hex.PermGroup.Group.setTransporterBudgeted returns an element, a proof that there is none, or a report that the search was not finished.

A partial result proves only what it contains. A subgroup found by an unfinished search may be smaller than the answer, and a derived series cut off before it reaches the trivial group does not show that the group is not solvable.