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: [email protected]
Reporter: [email protected]
CC: [email protected], [email protected]
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.
_______________________________________________
LLVMbugs mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/llvmbugs
