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

### 663. Complexity Requirements

Section: 16.3.2.4 [structure.specifications] Status: NAD Submitter: Thomas Plum Opened: 2007-04-16 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [structure.specifications].

View all other issues in [structure.specifications].

View all issues with NAD status.

Discussion:

16.3.2.4 [structure.specifications] para 5 says

> -5- Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees satisfy the requirements.

The following objection has been raised:

> The library clauses suggest general guidelines regarding complexity, but we have been unable to discover any absolute hard-and-fast formulae for these requirements. Unless or until the Library group standardizes specific hard-and-fast formulae, we regard all the complexity requirements as subject to a "fudge factor" without any intrinsic upper bound.

[Plum ref _23213Y31 etc]

Proposed resolution:

Rationale:

Kona (2007): No specific instances of underspecification have been identified, and big-O notation always involves constant factors.