From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31659 invoked by alias); 17 Apr 2008 20:39:59 -0000 Received: (qmail 31387 invoked by uid 48); 17 Apr 2008 20:39:14 -0000 Date: Thu, 17 Apr 2008 20:39:00 -0000 Subject: [Bug libstdc++/35968] New: nth_element fails to meet its complexity requirements X-Bugzilla-Reason: CC Message-ID: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "sjhowe at dial dot pipex dot com" Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2008-04/txt/msg01256.txt.bz2 nth_element in 4.3.0 fails to meet its complexity requirements. This is basically intraselect by Dave Musser. The question is "What algorithm should you switch to when quickselect fails?" In the codebase __heapselect() is called. But this in O(N * log N). __heapselect() is O(middle-first) + O((last-middle) * log(last-first)) which is O(N * log N) and the C++ standard requires nth_element to be O(N). __heapselect() is no use at all here. Better still is median-of-medians of groups of 5 (and plenty of proofs that it is O(N)) or approximate median finding and that is still O(N) See www.cs.wpi.edu/~hofri/medsel.pdf In the best or average case, intraselect is O(N) partitioning + O(1) finding a suitable partition element In the worse case, intraselect is O(N) partitioning + O(N) finding a suitable partition element Stephen Howe -- Summary: nth_element fails to meet its complexity requirements Product: gcc Version: 4.3.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: sjhowe at dial dot pipex dot com http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968