This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

### 2949. Unclear complexity requirements: space vs. time

Section: 16 [library] Status: New Submitter: Jens Maurer Opened: 2017-03-20 Last modified: 2017-07-15

Priority: 4

View other active issues in [library].

View all other issues in [library].

View all issues with New status.

Discussion:

This is from editorial issue #1088:

It is not always made explicit whether the requirement is referring to time or space complexity, or both.

> "Linear time." vs. "Linear."
> "Constant time." vs. "Constant."

16.3.2.4 [structure.specifications] says that the Complexity element specifies "the time and/or space complexity of the function", so being explicit about this would be good.

Examples:

- [sequence.reqmts] `a.clear()`

- [deque.cons]

- [vector.cons]

- [map.cons]

- [multimap.cons]

- [set.cons]

- [multiset.cons]

- [unord.map.cnstr]

- [unord.multimap.cnstr]

etc.

[2017-07 Toronto Wed Issue Prioritization]

Priority 4; Robert to look at

Proposed resolution: