Lesson
Completing a Set Takes Longer Than You Think
Filling in the last few items of a collection costs far more than the early ones, because duplicates pile up near the end.
By the Math Says Yes editorial team
Human-reviewed under our source and correction standards.
How we review content
The n·ln n rule
It feels natural to assume that collecting n different items takes roughly n tries. It does not. When each try gives you a uniformly random item, completing the set takes about n times the natural logarithm of n. For a set of 50, that is around 225 tries, not 50. The reason is that you keep drawing items you already own. Early on almost every draw is new, so the count climbs quickly, but progress slows down sharply as the set fills, because the of pulling something missing keeps shrinking. The bigger the set, the worse this gap between n and n·ln n becomes.
The cruel tail
The end is where the cost hides. Suppose you have all but one of n items. Every draw is now the missing item only with 1 over n, and anything else is a duplicate. The number of tries you need follows from that single chance: on it takes about n draws just to land that final item. So in a 50-item set, the last sticker alone averages around 50 packs, while the first half of the set arrived in a small fraction of that. The tail is not a rounding detail. It is the most expensive stretch of the whole effort, and it is exactly the part our planning tends to ignore.
Why trading wins
If duplicates make the tail expensive, then getting rid of duplicates makes it cheap. When you trade a doubled item with another collector who needs it for one you are missing, you collapse the slow part of the problem. Two collectors swapping their spares each skip the punishing wait for the few rare items, because your surplus is someone else's gap and vice versa. This is the math behind sticker-swap culture: the schoolyard tradition of trading duplicates is not just social, it is the single most effective way to beat the n·ln n cost. A market of traders turns a brutal individual tail into a quick collective finish.
Where it appears
The same shape shows up far beyond sticker albums. Loot boxes and gacha games hand out random rewards, so completing a roster of characters or cards runs into exactly this tail, which is part of why the last few are so frustrating to chase. Software testing meets it too: if a program has many rare code paths and your inputs hit them at random, covering all of them takes far longer than the path count suggests, and the last untested branch can be stubbornly hard to trigger. Whenever you need every item from a fixed set and you collect them at random, expect the finish line to sit much farther out than the size of the set alone implies.
FAQ
Does a bigger set get disproportionately harder to finish?
Yes. Completion scales with n times ln n rather than n, so doubling the set size more than doubles the tries you need on average. The logarithmic factor grows with n, which is why large collections feel so punishing near the end.
Why does swapping duplicates help so much?
Because duplicates are precisely what makes the tail expensive. Trading your spares for items you lack removes the long wait for rare missing pieces, since your surplus fills another collector's gap and theirs fills yours. A trading market converts a slow individual finish into a fast shared one.
Try the idea
Coupon collector
Open packs and watch the last few stickers stall.
0%
% complete
0
packs opened
91
expected to finish
The first stickers come fast, but near the end almost every pack is a duplicate — the last item alone takes about as many packs as the whole set has items.
Quick Check
You have 49 of 50 stickers. With 1 random sticker per draw, how many more draws until the last one, on average?
A
About 50 draws.
B
About 2 draws.
C
About 5 draws.