Project: |
Programming Language C++ |

Document Number: |
WG21/P0523r0 |

Date: |
2016-11-11 |

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

Target audience: |
SG1, LWG |

# 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

Thanks to Pete Becker for help with the wording.