Analysis of Bucket Sort
lAssume that the
number of data elements is comparable to,
or larger than, the number of buckets.
lGo through the data once, putting each element in the corresponding list.
This is O(n).
lConcatenate the resulting lists.
This is also O(n).
lGo through the data once, putting each element in the corresponding list.
This is O(n).
lConcatenate the resulting lists.
This is also O(n).
lTherefore we have
O(n) overall.
lRemember that
bucket sorting makes special assumptions
about the data.