# How many iterations does it take to cover a range with random values? [duplicate]

This question already has an answer here:

Let's say I have a random number generator that generates integers uniformly from 0 to n-1 (where n is some positive integer). What is the expected number of iterations after which all the values 0..n-1 will be generated? I did some simulations and the results seem close to n*ln(n), but I wonder how to solve it mathematically.
Possibly related SO question

## marked as duplicate by joriki probability StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 18 '16 at 1:08

This is known as the coupon collector's problem. See the link for details and references. You are right that asymptotically, the expected number of trials needed grows as $n \ln n$ (plus lower order terms).