5 ms·
Technically, the lower bound is log2(n!), which is slightly less than n * log2(n). According to the table of experimental results, the algorithm described in t
by teraflop 11y ago
Technically, the lower bound is log2(n!), which is slightly less than n * log2(n).
According to the table of experimental results, the algorithm described in this paper and two of its competitors can all do better than n * log2(n) bits.
- darkmighty 11y agoAh yes log2(n!) is O(n.log2(n)) bits, not actually n.log2(n) bits. From Stirling's approximation* it seems it's more like n.log2(n)-n+O(log2(n)) bits. https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation