Editing Bucket sort (section)

=== Average-case analysis ===
Consider the case that the input is uniformly distributed. The first step, which is '''initialize''' the buckets and '''find the maximum key value''' in the array, can be done in <math>O(n)</math> time. If division and multiplication can be done in constant time, then '''scattering''' each element to its bucket also costs <math>O(n)</math>. Assume insertion sort is used to sort each bucket, then the third step costs <math>O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)</math>, where <math>n_i</math> is the length of the bucket indexed <math>i</math>. Since we are concerning the average time, the expectation <math>E(n_i^2)</math> has to be evaluated instead. Let <math>X_{ij}</math> be the random variable that is <math>1</math> if element <math>j</math> is placed in bucket <math>i</math>, and <math>0</math> otherwise. We have <math>n_i = \sum_{j=1}^n X_{ij}</math>. Therefore,

:<math>\begin{align}
E(n_i^2) & = E\left(\sum_{j=1}^n X_{ij} \sum_{l=1}^n X_{il}\right) \\
& = E\left(\sum_{j=1}^n \sum_{l=1}^n X_{ij}X_{il}\right) \\
& = E\left(\sum_{j=1}^n X_{ij}^2\right) + E\left(\sum_{1\leq j,l\leq n}\sum_{j\neq l}X_{ij}X_{il}\right)
\end{align} </math>

The last line separates the summation into the case <math>j=l</math> and the case <math>j\neq l</math>. Since the chance of an object distributed to bucket <math>i</math> is <math>1/k</math>, <math>X_{ij} </math> is 1 with probability <math>1/k</math> and 0 otherwise.

:<math>E(X_{ij}^2) = 1^2\cdot \left(\frac{1}{k}\right) + 0^2\cdot \left(1-\frac{1}{k}\right) = \frac{1}{k}</math>
:<math>E(X_{ij}X_{ik}) = 1\cdot \left(\frac{1}{k}\right)\left(\frac{1}{k}\right) = \frac{1}{k^2} </math>

With the summation, it would be

:<math>E\left(\sum_{j=1}^n X_{ij}^2\right) + E\left(\sum_{1\leq j,k\leq n}\sum_{j\neq k}X_{ij}X_{ik}\right) = n\cdot\frac{1}{k} + n(n-1)\cdot\frac{1}{k^2} = \frac{n^2+nk-n}{k^2}</math>

Finally, the complexity would be <math>O\left(\sum_{i=1}^kE(n_i^2)\right) = O\left(\sum_{i=1}^k \frac{n^2+nk-n}{k^2}\right) = O\left(\frac{n^2}{k}+n\right) </math>.

The last step of bucket sort, which is '''concatenating''' all the sorted objects in each bucket, requires <math>O(k)</math> time. Therefore, the total complexity is <math>O\left(n+\frac{n^2}{k}+k\right)</math>. Note that if k is chosen to be <math>k = \Theta(n)</math>, then bucket sort runs in <math>O(n)</math> average time, given a uniformly distributed input.<ref name="lfcs" />