# Tag Info

0

The naive solution may be n log n bits. But for the first number you have n choices; you have n-1 choices for the second number, n-2 choices for the third number etc. So log(n!) bits, rounded up to the next integer, would be a possibility. In practice, if you want the lookup to be fast, looking up number k should locate a range of bits that represent some ...

1

This is equivalent to storing a permutation of $n$ items in memory. There are in general, $n!$ ($n$ factorial) such permutations, and it is well known that $\log(n!)=\Theta(n\log(n))$. Hence, you will need at least $\Omega(n\log(n))$ bits to represent the permutations (which is what you get from the naive solution). So without even the requirement about the ...

Top 50 recent answers are included