Return-Path: Delivered-To: apmail-incubator-stdcxx-dev-archive@www.apache.org Received: (qmail 52764 invoked from network); 8 Feb 2006 02:00:21 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 8 Feb 2006 02:00:21 -0000 Received: (qmail 46749 invoked by uid 500); 8 Feb 2006 02:00:21 -0000 Delivered-To: apmail-incubator-stdcxx-dev-archive@incubator.apache.org Received: (qmail 46734 invoked by uid 500); 8 Feb 2006 02:00:20 -0000 Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: stdcxx-dev@incubator.apache.org Delivered-To: mailing list stdcxx-dev@incubator.apache.org Received: (qmail 46723 invoked by uid 99); 8 Feb 2006 02:00:20 -0000 X-ASF-Spam-Status: No, hits=0.0 required=10.0 tests= X-Spam-Check-By: apache.org Received: from [192.87.106.226] (HELO ajax.apache.org) (192.87.106.226) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 07 Feb 2006 18:00:20 -0800 Received: from ajax.apache.org (ajax.apache.org [127.0.0.1]) by ajax.apache.org (Postfix) with ESMTP id AFE59CB for ; Wed, 8 Feb 2006 02:59:59 +0100 (CET) Message-ID: <258797920.1139363999718.JavaMail.jira@ajax.apache.org> Date: Wed, 8 Feb 2006 02:59:59 +0100 (CET) From: "Martin Sebor (JIRA)" To: stdcxx-dev@incubator.apache.org Subject: [jira] Commented: (STDCXX-138) Complexity tests are not strict enough for some algorithms when the expected complexity is a function of the given sequence length (not exact count) In-Reply-To: <1639373049.1139306400638.JavaMail.jira@ajax.apache.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N [ http://issues.apache.org/jira/browse/STDCXX-138?page=comments#action_12365508 ] Martin Sebor commented on STDCXX-138: ------------------------------------- See this thread for background: http://mail-archives.apache.org/mod_mbox/incubator-stdcxx-dev/200602.mbox/%3c43E80945.4060503@roguewave.com%3e > Complexity tests are not strict enough for some algorithms when the expected complexity is a function of the given sequence length (not exact count) > ---------------------------------------------------------------------------------------------------------------------------------------------------- > > Key: STDCXX-138 > URL: http://issues.apache.org/jira/browse/STDCXX-138 > Project: C++ Standard Library > Type: Improvement > Components: 25. Algorithms > Versions: 4.1.3 > Environment: all > Reporter: Anton Pevtsov > Priority: Minor > Fix For: 4.1.4 > > 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. -- This message is automatically generated by JIRA. - If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa - For more information on JIRA, see: http://www.atlassian.com/software/jira