[STDCXX-138] algorithms complexity tests not strict enough

• Type: Improvement
• Status: Open
• Priority: Minor
• Resolution: Unresolved
• Affects Version/s: 4.1.3, 4.1.4, 4.2.0
• Fix Version/s: 4.3.0
• Component/s: Tests

Environment

all

• Assignee: Unassigned
• Reporter: Anton Pevtsov
• Created: 07/Feb/06 18:59
• Updated: 16/Jan/08 22:13

Description

Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.

It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.

Issue Links

• is related to: STDCXX-397 std::sort introsort implementation error