<html>
<head>
<base href="http://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - `std::make_heap` has worst case time complexity of O(n log n) rather than the standard mandate O(n)"
href="http://llvm.org/bugs/show_bug.cgi?id=20161">20161</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>`std::make_heap` has worst case time complexity of O(n log n) rather than the standard mandate O(n)
</td>
</tr>
<tr>
<th>Product</th>
<td>libc++
</td>
</tr>
<tr>
<th>Version</th>
<td>3.4
</td>
</tr>
<tr>
<th>Hardware</th>
<td>Macintosh
</td>
</tr>
<tr>
<th>OS</th>
<td>MacOS X
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>All Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>netheril96@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu, mclow.lists@gmail.com
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=12718" name="attach_12718" title="Test source code">attachment 12718</a> <a href="attachment.cgi?id=12718&action=edit" title="Test source code">[details]</a></span>
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
<a href="http://stackoverflow.com/questions/24475056/is-libcs-implementation-of-stdmake-heap-nonconformant">http://stackoverflow.com/questions/24475056/is-libcs-implementation-of-stdmake-heap-nonconformant</a>.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>