Title
[fund.ts] Incorrect complexity for sample() algorithm
Status
open
Section
[alg.random.sample]
Submitter
Joe Gottman

Created on 2014-12-17.00:00:00 last changed 81 months ago

Messages

Date: 2016-08-12.18:08:55

Proposed resolution:

This wording is relative to N4335 in regard to fundamental-ts changes.

  1. Change [alg.random.sample] p5 to read:

    -5- Complexity: 𝒪(nlast - first).

Date: 2015-03-22.19:07:57

[ 2015-02, Cologne ]

AM: I suggest we make this a DR against the Fundamentals TS.
GR: Agreed, this is a no-brainer.

Date: 2016-08-12.18:08:55

Addresses: fund.ts

According to paragraph 10.1 of the Library Fundamentals 1 draft, the complexity of the new std::experimental::sample template function is 𝒪(n). Note that n is actually a parameter of this function, corresponding to the sample size. But both common algorithms for sampling, the selection algorithm and the reservoir algorithm, are linear with respect to the population size, which is often many orders of magnitude bigger than the sample size.

History
Date User Action Args
2017-07-30 20:10:41adminsetstatus: wp -> open
2015-05-22 18:31:21adminsetstatus: ready -> wp
2015-03-22 19:07:57adminsetmessages: + msg7247
2015-03-22 19:07:57adminsetstatus: new -> ready
2015-01-18 19:29:00adminsetmessages: + msg7220
2014-12-17 00:00:00admincreate