[OT] Algorithm question

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 1 May 2017 at 08:42:05 UTC, John Colvin wrote:
> I like this one (warning, just thought of, untested):
>
> auto r = ... /* elements of A */
> auto nRemaining = r.length;
> while (nRemaining) {
> 	auto i = uniform(0, nRemaining);
> 	if (P(r[i])) return r[i];
> 	else swap(r[i], r[--nRemaining]);
> }


Yes, this is the standard text-book way of doing it, still O(N) 
of course. The other standard-text-book way is to generate an 
array of indexes and mutate that instead, still O(N). If you 
cache in a heap you get O(N log N).

Anyway, this kind of worst case analysis doesn't really help. And 
neither does average case, which will be O(1) assuming 50% match 
P.

So you need is to specify what kind of average case analysis you 
want. For instance expressed as f(N,S)  where N is the number of 
elements and S is the number of elements that satisfies P.