Andrei, asta ziceam si eu in postul anterior.
Problema este clasica si apare sub denumirea "cupon colector's problem"
http://en.wikipedia.org/wiki/Coupon_collector's_problemSolutia intreaga pe scurt:
(1) E(colectia cu n elemente) = E(1 element) + E(al 2-lea element) + .. + E(al n-lea element)
(2) P(al x+1-lea element, avand deja x elemente) = (n - x) / n
E(eveniment cu probabilitatea p) = 1 * p + (1 - p) (1 + E(eveniment cu probabilitatea p)) rezolvand ecuatia obtinem E(eveniment cu probabilitatea p) = 1 / p (3)
(1), (2), (3) => E(colectia cu n elemente) = n(1 + 1/2 + .. + 1/n) (4)
1/x <= 1/[ x ] <= 1/(x - 1)
integram de la 2 la n + 1 => ln (n + 1) - ln 2 < suma i=2,n 1/i < ln n => O(1 + 1/2 + .. + 1/n) = O(log n) (5)
(4), (5) => O(E(colectia cu n elemente)) = O(n log n)