Question bank — Bucket sort — uniform distributions

False. The $O(n)$ is expected time under uniform input; adversarial or skewed data can dump every element into one bucket, giving $O(n^2)$.

False. It doesn't violate it — it sidesteps it. The scatter step uses each value as an address (not a comparison), so the bound about comparison sorts simply doesn't apply.

False. On average one per bucket, but randomness clumps them: some buckets get 0, some get 2 or 3. That variance is exactly what the $E[n_i^2]=2-1/n$ term measures ($n_i$ = count in bucket $i$).

True (partially). The scatter is not comparison-based, but the per-bucket sort (usually Insertion sort) does compare. Since each bucket is tiny, those comparisons cost $O(1)$ each on average.

True. If elements keep their insertion order within a bucket and each bucket uses a stable internal sort, equal keys preserve their original relative order.

False. Creating and concatenating buckets costs $O(\#\text{buckets})$. Far more than $n$ buckets wastes time scanning empty ones; the sweet spot stays $\approx n$.

False. You must know (or estimate) the value range $[lo,hi)$ to normalize into $[0,1)$ via $\lfloor n(x-lo)/(hi-lo)\rfloor$; otherwise you cannot compute a bucket index.

False. Expected size is constant, but with random inputs the largest bucket grows slowly — $\Theta (\log n/\log \log n)$ — and with adversarial input it can be $n$. "Expected" is not "maximum" (see WHY8 for why that particular growth rate).

False, but related. Counting sort is bucket sort's special case where each bucket holds one integer value (bucket size 1), so no internal sort is needed at all.

Error: when $x=1.0$, int(n*1.0) $=n$ — an index one past the last valid bucket ($n-1$). Use half-open $[0,1)$ or clamp with min(idx, n-1).

Error: $E[X^2]\ne (E[X]{)}^2$ in general. The missing variance term matters: $E[n_i^2]=\mathrm{Var}(n_i)+(E[n_i]{)}^2=(1-1/n)+1=2-1/n$, not $1$ (recall $n_i$ = count in bucket $i$).

Error: dividing by $n$ shrinks values toward $0$, so every $x\in [0,1)$ maps to bucket $0$. You want to stretch the interval by $n$ (multiply), not compress it.

Error: the $O(n)$ needs a known, roughly uniform distribution. On unknown or skewed data a comparison sort's guaranteed $O(n\log n)$ is safer than bucket sort's $O(n^2)$ worst case.

Error: any $O(m^2)$ sort on a bucket of expected constant size $m$ costs $O(1)$ expected. The choice of internal sort doesn't change the linear expected total; only the input distribution does.

Error: buckets fill uniformly in count, but the two or three values inside one bucket are still unordered. You must sort within each bucket before concatenating.

Uniformity makes each element land in bucket $i$ with equal probability $p=1/n$; over $n$ elements $E[n_i]=np=1$. Non-uniform input skews these probabilities.

Each of $n$ elements independently either lands in bucket $i$ (probability $1/n$) or not — that's exactly $n$ independent yes/no trials, the definition of a Binomial distribution.

Each $E[n_i^2]<2$ is constant, and there are $n$ buckets, so ${\sum }_{i}E[n_i^2]<2n=O(n)$. Constant-per-bucket times $n$ buckets is linear.

Buckets are tiny (expected size $\approx 1$), and Insertion sort has minimal overhead and is fast on small, near-sorted lists — quicksort's recursion overhead would dominate at that scale.

Both compute an address directly from the value (index vs. hash bucket) instead of comparing. The difference: sorting needs order-preserving buckets; hashing only needs collision management.

That bound counts only comparison operations in the decision-tree model. Bucket sort's scatter extracts information from the value itself, an operation outside that model, so the bound doesn't constrain it.

With $k\ll n$ buckets each holds $\approx n/k$ items, pushing internal sort toward $O((n/k{)}^2)$ per bucket — growing with $n$. Matching buckets to elements keeps each bucket $O(1)$.

This is the classic "balls into bins" result. Let $m$ be a candidate bucket-size threshold — the size we ask whether any bucket exceeds. The chance any fixed bucket exceeds size $m$ is roughly $1/m!$, and with $n$ buckets the maximum settles where $n/m!\approx 1$. Solving $m!\approx n$ gives $m\approx \log n/\log \log n$ — small but growing, so the max isn't constant even though the mean is.

Bucket creation, iteration, and concatenation each touch every bucket once, so their cost is $O(\#\text{buckets})$ regardless of how many are empty. With $B\gg n$ buckets you already spend $O(B)$ just scanning, which dominates the $O(n)$ scatter — the extra empty buckets buy no fewer collisions once you are past one-per-element, only wasted passes and memory.

They all map to the same bucket, which then holds $n$ items — internal sort becomes $O(n^2)$. This is the degenerate worst case even though the values are "nice".

You create $0$ buckets and the loops never run; output is the empty list. No index is ever computed, so no division-by-zero or out-of-range issue arises.

$\lfloor 10\cdot 0.3\rfloor =3$ cleanly, because the floor sends boundary points to the upper bucket. Floating-point rounding of $0.3$ can rarely nudge it, so half-open intervals plus clamping stay safest.

One bucket, one element, index $\lfloor 1\cdot x\rfloor =0$; internal sort is trivial and output equals input. The linear bound holds vacuously.

Values outside $[0,1)$ produce indices that are negative or $\ge n$ — out-of-range crashes. Always apply $\lfloor n(x-lo)/(hi-lo)\rfloor$ first.

A negative $x$ makes $n\cdot x$ negative; int truncates toward zero (giving $0$) while $\lfloor \cdot \rfloor$ floors down (giving a negative index that wraps to the list's end in Python or crashes elsewhere). Normalizing by the true $lo$ removes the sign before bucketing.

Then you don't need floats or internal sorting — one bucket per integer value gives Counting sort, the size-1-bucket special case, at guaranteed $O(n+\text{range})$.

The normalization $\lfloor n(x-lo)/(hi-lo)\rfloor$ divides by zero. Guard for it: if $hi=lo$ all values are identical, so the array is already sorted — return it directly (or drop everything into bucket $0$) instead of computing the index.