New answers tagged lower-bounds
-1
i was thinking quicksort. you select as pivot the element that just happens to be the middle element. compare the pivot to the remaining 4 items resulting in two piles to be sorted. each of those piles can be sorted in 1 comparison. unless i have made a terrible mistake, the 5 items were fully sorted in just 6 comparisons and i think that is the absolute ...
1
Stirling's formula shows that
$$
\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},
$$
where $H(p)$ is the binary entropy function:
$$
H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.
$$
In particular, this shows that for $k \geq 2$,
$$
\binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\...
Top 50 recent answers are included
