Re: sort_heap complexity guarantee

[François Dumont <frs dot dumont at gmail dot com>]

On 06/10/2014 23:05, Daniel Krügler wrote:
> 2014-10-06 23:00 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
> > On 05/10/2014 22:54, Marc Glisse wrote:
> > > On Sun, 5 Oct 2014, François Dumont wrote:
> > >
> > > >     I took a look at PR 61217 regarding pop_heap complexity guarantee.
> > > > Looks like we have no test to check complexity of our algos so I start
> > > > writing some starting with the heap operations. I found no issue with
> > > > make_heap, push_heap and pop_heap despite what the bug report is saying
> > > > however the attached testcase for sort_heap is failing.
> > > >
> > > >     Standard is saying std::sort_heap shall use less than N * log(N)
> > > > comparisons but with my test using 1000 random values the test is showing:
> > > >
> > > > 8687 comparisons on 6907.76 max allowed
> > > >
> > > >     Is this a known issue of sort_heap ? Do you confirm that the test is
> > > > valid ?
> > > I would first look for confirmation that the standard didn't just forget a
> > > big-O or something. I would expect an implementation as n calls to pop_heap
> > > to be legal, and if pop_heap makes 2*log(n) comparisons, that naively sums
> > > to too much. And I don't expect the standard to contain an advanced
> > > amortized analysis or anything like that...
> > 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!) ?
> François, could you please submit a corresponding LWG issue by sending
> an email using the recipe described here:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#submit_issue
>
> ?
I just did requesting to use 2N log(N).

And is it ok to commit those ?

François