Re: About the expected number of comparisons for n keys into k buckets

in reply to About the expected number of comparisons for n keys into k buckets

I get the same expression you do.

For one bucket of x elements,

1st requires 1 comparison
2nd requires 2 comparisons
3rd requires 3 comparisons
...
xth requires x comparisons

Total comparisons
= x + x-1 + ... + 2 + 1
= x(x+1)/2

If there are k buckets of n/k elements,
 
Total comparisons
= k * (n/k) * ((n/k)+1) / 2
= n(n + k)/2k
[download]

Comment on Re: About the expected number of comparisons for n keys into k buckets Download Code

Replies are listed 'Best First'.
Re^2: About the expected number of comparisons for n keys into k buckets by PerlOnTheWay (Monk) on Jul 28, 2011 at 02:52 UTC
Oh, I spot what's wrong here,it should be: X1(X1+1)/2 + ... Xk(1+Xk)/2 = n/2 + (X1^2+X2^2+...+Xk^2)/2 Let (1) denote the above expression. Now I've no idea how to calculate the expected value of (1)....	[reply]

In Section Seekers of Perl Wisdom