Bucket Sort: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
<font color=darkgray>Require knowledge of the probabilistic distribution of the number in the input array. It can sort n real numbers uniformly distributed in the half-open interval [0, 1) in average-case O(n) time.</font> | <font color=darkgray> | ||
TODO [[CLRS]] page 200. | |||
Require knowledge of the probabilistic distribution of the number in the input array. It can sort n real numbers uniformly distributed in the half-open interval [0, 1) in average-case O(n) time.</font> | |||
{| | {| | ||
Latest revision as of 01:19, 10 August 2018
Internal
Overview
TODO CLRS page 200.
Require knowledge of the probabilistic distribution of the number in the input array. It can sort n real numbers uniformly distributed in the half-open interval [0, 1) in average-case O(n) time.
| Worst-case time | Θ(n2) |
| Average-case time | Θ(n)) |
| Best-case time |