Average time behavior of distributive sorting algorithms

In this paper we investigate the expected complexityE(C) of distributive (“bucket”) sorting algorithms on a sampleX ₁, ...,X _n drawn from a densityf onR ¹. Assuming constant time bucket membership determination and assuming the use of an average timeg(n) algorithm for subsequent sorting within each bucket (whereg is convex,g(n)/n↑∞,g(n)/n ² is nonincreasing andg is independent off), the following is shown:

1. Iff has compact support, then ∫g(f(x))dx<∞ if and only ifE(C)=0(n).
2. Iff does not have compact support, then \(E(C)/n\xrightarrow{n}\infty \) .

No additional restrictions are put onf.