[LLVMbugs] [Bug 20161] New: `std::make_heap` has worst case time complexity of O(n log n) rather than the standard mandate O(n)
bugzilla-daemon at llvm.org
bugzilla-daemon at llvm.org
Mon Jun 30 03:47:31 PDT 2014
http://llvm.org/bugs/show_bug.cgi?id=20161
Bug ID: 20161
Summary: `std::make_heap` has worst case time complexity of O(n
log n) rather than the standard mandate O(n)
Product: libc++
Version: 3.4
Hardware: Macintosh
OS: MacOS X
Status: NEW
Severity: normal
Priority: P
Component: All Bugs
Assignee: unassignedclangbugs at nondot.org
Reporter: netheril96 at gmail.com
CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
Classification: Unclassified
Created attachment 12718
--> http://llvm.org/bugs/attachment.cgi?id=12718&action=edit
Test source code
The current `std::make_heap` in libc++ uses an algorithm equivalent to
successively pushing into the heap, which has a worse case time complexity of
O(n log n), while both GCC and MSVC's implementation uses an algorithm that
builds the heap from bottom up, with complexity O(n).
The standard specifies that no more than 3n comparisons can be made in
`std::make_heap`. The attach test file, however, prints 480 (greater than
3*100) with libc++, but 144 with libstdc++, confirming that it is indeed a bug
in libc++'s implementation.
A longer discussion can be seen at
http://stackoverflow.com/questions/24475056/is-libcs-implementation-of-stdmake-heap-nonconformant.
--
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140630/3419bab5/attachment.html>
More information about the llvm-bugs
mailing list