Which sorting algorithm has an O(n) average-case time complexity by assuming the input is uniformly distributed over the interval [0, 1)?
Show answer
Bucket sort
Bucket sort divides the interval into n equal-sized sub-intervals (buckets) and distributes the input elements into them. Since the input is uniform, the number of elements per bucket is small, allowing for linear total sorting time.
Also asked as:
- Which sorting algorithm achieves linear average-case time by distributing input elements into n equal-sized sub-intervals?