5 ms·
The space requirement is surely impossible to fulfil generically. As soon as you do any sort of compression you make it possible for two elements to map to the
by sweezyjeezy 11y ago
The space requirement is surely impossible to fulfil generically. As soon as you do any sort of compression you make it possible for two elements to map to the same thing. Unless you know that M << N, in which case you can just save exactly one element, and just replace it every time you see a new one!
- deleted 11y ago[deleted]
- mistercow 11y agoThat's basically true. Technically you can meet these requirements by exploiting the false negatives loophole, but if the data structure can ever report that it contains a size M element, it will need O(M) space.