 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 formula_3 time.If division and multiplication can be done in constant time, then scattering each element to its bucket also costs formula_3.