On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote: > Which elements of A satisfy P(x) is not known ahead of time, > nor is the > relative proportion of elements that satisfy P(x) or not. O(N) given P(x)===false for all x... What you want is probably average case analysis, not worst case?