Bucket sort — uniform distributions: Foundations

This page assumes nothing. If the parent note used a symbol, we build it here, from the picture up, in an order where each idea leans only on the ones before it.

1. A "list" (array) and its length $n$

Picture a row of boxes side by side. If there are ten boxes, $n = 10$ . That single number $n$ will appear everywhere: number of items, number of buckets, and the stretch factor when we compute an address.

Why the topic needs it. Bucket sort creates exactly $n$ buckets (one per expected element). So $n$ is doing double duty — it counts the input and sizes the workspace.

Figure — Bucket sort — uniform distributions

2. The half-open interval $[0, 1)$

Picture a ruler from 0 to 1. The left tip is a filled dot (included), the right tip is a hollow dot (excluded).

Why the topic needs it. Uniform inputs are stated to live in $[0, 1)$ precisely so the address formula never overflows.

3. The floor function $⌊ \cdot ⌋$

Picture a staircase where each step is a whole number. Wherever $x$ stands on the ramp, floor drops it straight down to the step beneath its feet.

The two bent bars $⌊ ⌋$ (like brackets missing their tops) are the floor symbol. In code this is int() for non-negative numbers.

Why the topic needs it. A bucket index must be a whole number ( $0, 1, 2, \dots$ ). The value $n \cdot x$ is usually a decimal (e.g. $7.2$ ). Floor converts "somewhere in the range" into "which whole box" — it is the tool that turns a continuous value into a discrete address.

4. Subscripts: $x_{i}$ and $n_{i}$

Picture each box in the row wearing a numbered sticker on its front. $x_{i}$ points at the value inside; $n_{i}$ counts how many values sit in bucket number $i$ .

Why the topic needs it. The proof sums over all buckets: $\sum_{i} n_{i}^{2}$ . Without a name for "bucket $i$ 's load," we could not write that sum.

5. Putting it together: the address $⌊ n \cdot x ⌋$

Now every piece from §1–§4 combines into the single most important line of the whole topic.

WHAT this does, step by step (see figure):

Stretch: multiply $x$ by $n$ . This blows the tiny ruler $[0, 1)$ up to the wide ruler $[0, n)$ .
Drop: floor the result. Every value in $[0, 1)$ now maps to one of the whole numbers $0, 1, \dots, n - 1$ .

WHY multiply then floor and not something else? We want equal-width value slots to map to consecutive buckets. Multiplying by $n$ makes each slot of width $1/ n$ become width $1$ ; flooring then reads off which unit-slot you're in. No comparisons, no searching — pure arithmetic. That is the "value-as-address" trick.

6. "Uniform distribution" — the assumption that makes it fast

Picture rain falling evenly across a flat roof: every tile catches about the same number of drops. Contrast with rain blown into one corner — that corner floods (a skewed distribution).

Why the topic needs it. Even rain → even bucket loads → each $n_{i} \approx 1$ → each bucket trivially cheap to sort. This is the entire reason bucket sort beats $O (n lo g n)$ . Break the assumption (all drops in one corner) and one bucket holds all $n$ items → the $O (n^{2})$ worst case.

Formally, "each item independently lands in bucket $i$ with probability $p = 1/ n$ " is the mathematical shape of "uniform." That statement is exactly what feeds the Binomial distribution used in the proof.

7. Big-O: $O (n)$ , $O (n^{2})$ , $O (n lo g n)$

Picture three curves climbing from the origin: a straight line ( $n$ ), a gently-bending sweep ( $n lo g n$ ), and a steep parabola ( $n^{2}$ ). Bucket sort aims for the straight line and falls to the parabola when the distribution assumption dies.

Why the topic needs it. The whole payoff is a claim about scaling: "expected $O (n)$ ." You cannot state, prove, or appreciate that without this notation.

n

stand for in bucket sort?

The number of input values — and also the number of buckets we create.

1.0

inside the interval

[0, 1)

No — the round bracket ) excludes 1; only values up to but not reaching 1 are allowed.

Compute

⌊ 3.9 ⌋

3

— floor rounds down, never up.

⌊ \cdot ⌋

the same as rounding?

No — floor always goes down (

2.7 \to 2

), rounding can go up (

2.7 \to 3

What does the subscript in

n_{i}

mean?

"Bucket number

i

" —

n_{i}

is how many items landed in that specific bucket.

Which bucket does

x = 0.45

go to when

n = 10

⌊ 10 \cdot 0.45 ⌋ = ⌊ 4.5 ⌋ = 4

Why multiply by

n

before flooring?

To stretch

[0, 1)

up to

[0, n)

so each width-

1/ n

value slot becomes one whole bucket.

In words, what does "uniform distribution" guarantee about buckets?

Every bucket is equally likely, so loads come out roughly even — about one item each.

What does

O (n)

mean compared to

O (n^{2})

Linear vs quadratic — doubling input doubles

O (n)

time but quadruples

O (n^{2})

time.

What does

\sum_{i = 0}^{n - 1} n_{i}^{2}

compute?

The total per-bucket sorting work, summed over every bucket.

What is

E [X]

in plain words?

The long-run average value of the random quantity

X

over many trials.

Foundations — Bucket sort — uniform distributions

1. A "list" (array) and its length $n$

2. The half-open interval $[0, 1)$

3. The floor function $⌊ \cdot ⌋$

4. Subscripts: $x_{i}$ and $n_{i}$

5. Putting it together: the address $⌊ n \cdot x ⌋$

6. "Uniform distribution" — the assumption that makes it fast

7. Big-O: $O (n)$ , $O (n^{2})$ , $O (n lo g n)$

8. The sum symbol $\sum$ and expectation $E [\cdot]$

Prerequisite map

Equipment checklist