Title
Complexity Requirements
Status
nad
Section
[structure.specifications]
Submitter
Thomas Plum

Created on 2007-04-16.00:00:00 last changed 159 months ago

Messages

Date: 2011-03-05.00:04:13

Rationale:

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

Date: 2007-04-16.00:00:00

[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]

History
Date User Action Args
2011-03-05 00:04:13adminsetmessages: + msg5585
2007-04-16 00:00:00admincreate