3 ms·
I'm pretty sure that computing N choose k requires O(k log N) memory to store the result (for N >> k). Neat trick though.
by scythe 9y ago
I'm pretty sure that computing N choose k requires O(k log N) memory to store the result (for N >> k). Neat trick though.
- nightcracker 9y agoI should've said O(small), I'm comparing to the solution in the OP, which computes all possible combinations in a lookup table.