Project: |
Programming Language C++ |

Document Number: |
WG21/P0523R1 |

Date: |
2017-03-01 |

Author: |
Detlef Vollmann, dv@vollmann.ch |

Target audience: |
SG1, LWG |

# P0523R1: 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`.

## Acknowledgments

Thanks to Pete Becker for help with the wording.