0

So I have a set of positive integers S (like {1, 5, 9, 29, 12}).
With this set, I want to construct an algorithm that can, later on, tell me, given any element, its position on the set in constant time (always the same regardless of how big the set was).
Kind of like a hashmap, but those are O(1) in average, not always. There's always a chance for collisions.
One could build an array with size max(S) and store, in each element's index, its position. But this would take as much space as the biggest element in S (not ideal; the size should be linear to the size of S).

pollatron
  • 23
  • 1
    What you're asking isn't entirely clear, but it sounds like you want a constant-time algorithm ("function") to sort a list of positive integers into increasing order. If that's indeed what you're asking, there's a well-known simple argument showing that no such algorithm exists (see e.g. https://cs.stackexchange.com/questions/150150/why-does-sorting-a-collection-have-on-log-n-complexity). – Prasiortle Feb 27 '24 at 00:57
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Feb 27 '24 at 01:23

0 Answers0