New answers tagged

-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