Comment by yunohn

> It checks a fixed sample of items (roughly 1%) regardless of size

> This provides O(1) performance

Wouldn’t 1% of N still imply O(N) performance?