This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: sort_heap complexity guarantee
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: François Dumont <frs dot dumont at gmail dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 8 Oct 2014 09:43:44 +0100
- Subject: Re: sort_heap complexity guarantee
- Authentication-results: sourceware.org; auth=none
- References: <5431A354 dot 2050404 at gmail dot com> <alpine dot DEB dot 2 dot 11 dot 1410052245150 dot 5366 at stedding dot saclay dot inria dot fr> <543302DF dot 7080607 at gmail dot com>
On 06/10/14 23:00 +0200, François Dumont wrote:
Good point, with n calls to pop_heap it means that limit must be
2*log(1) + 2*log(2) +... + 2*log(n) which is 2*log(n!) and which is
also necessarily < 2*n*log(n). I guess Standard comittee has forgotten
the factor 2 in the limit so this is what I am using as limit in the
final test, unless someone prefer the stricter 2*log(n!) ?
Ok to commit those new tests ?
Yes please - thanks.