Re: coupon collector problem

"yezi" <ye_line@hotmail.com> wrote in message
news:1133304625.063837.313260@z14g2000cwz.googlegroups.com...
> Hi: all:
>
> I am reading the paper" Practical Network Support for IP Traceback" ,
> in this paper , there is one sentence related to the " coupon collector
> problem", however I am new with that topic. Just paste the sentence
> here, what I want to ask, what is expension of d(ln(d)+o(1)) , how can
> draw the conclusion.
>
> Thanks
> "
> Finally,as per the well-known coupon collector problem, the number
> of trials required to select one of each of d equi-probable items
> is d(ln(d) + O(1))."

That last part is often referred to as "Big-O" notation, and while the full
explaination is significantly more complicated, for your purpose it is a
function defining the run-time. There are a number of things dropped from
the notation, in particular most constants and overpowered functions are
dropped (why is unimportant here). In order to graph the function choose a
small fixed number for O(1), generally numbers from 0 to 10 are good
candidates, this should give you a curve that after a period fits between x
and x^2, and in this case in particular I'd choose 0 as the base number,
just for the sake of a clean graph.
                Joe
Received on Sat Dec 3 04:20:25 2005