2463. [fund.ts] Incorrect complexity for sample() algorithm

Section: 10.3 [fund.ts::alg.random.sample] Status: TS Submitter: Joe Gottman Opened: 2014-12-17 Last modified: 2017-07-30

Priority: 0

View all issues with TS status.

Discussion:

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.

[2015-02, Cologne]

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

Proposed resolution:

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

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

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