Uploaded image for project: 'C++ Standard Library'
  1. C++ Standard Library
  2. STDCXX-138

algorithms complexity tests not strict enough

    XMLWordPrintableJSON

    Details

    • 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
    • Labels:
      None
    • Environment:

      all

      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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                pevtsov Anton Pevtsov
              • Votes:
                0 Vote for this issue
                Watchers:
                0 Start watching this issue

                Dates

                • Created:
                  Updated: