P0523r0: Wording for CH 10: Complexity of parallel algorithms

Proposed wording

In 25.2.5 [algorithms.parallel.overloads] add another paragraph after p2:

Unless otherwise specified, the complexity requirements of ExecutionPolicy algorithm overloads are relaxed from the complexity requirements of the overloads without as follows:
When the guarantee says "At most expr" or "Exactly expr" and doesn't specify the number of assignments or swaps, and expr isn't already an O-Notation, the complexity of the algorithm shall be "O(expr)".

In 25.4.4p4 [alg.transform], change:

Complexity: Exactly last1 - first1 applications of op or binary_op. This requirement also applies to the overload with an ExecutionPolicy.

In 25.5.4p8 [alg.merge], change:

Complexity: When enough additional memory is available, (last - first) - 1 comparisons. For the overloads with an ExecutionPolicy the complexity is O(last - first). If no additional memory is available, an algorithm with complexity N log(N) may be used, where N = last - first.

Acknowledgments