Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap with one slot for each possible integer. 2 billion different integers * 4 bytes per integer = 8 gigabytes....but it'd technically work. There has to be a better way to do this though, right?
One way to convince yourself it is not possible is to consider what it would enable. Assume there exists an O(1) algorithm for insertion into an unbounded sorted array, CONST_INSERT. Then we can define a O(n) sorting algorithm as follows:
- Let $L$ be an empty list $()$ and $U = (u_1, u_2, \ldots u_n)$ be an unsorted list.
- Iterate over $i: 1 \rightarrow n$, inserting $u_i$ into $L$ using CONST_INSERT
This produces a sorted array, since at the end of every iteration $i$, $L$ will be exactly a sorted list of $(u_1 \ldots u_i)$. And it will have a runtime of O(n).
From a practical perspective, if an O(n) sorting algorithm existed it would be very useful, so you'd likely know about it. From a theory perspective, resources like this might help you convince yourself that no such sorting algorithm could exist.
One thing before I explain:
HashMap doesn't use an array that big, it uses chaining, which is another concept you'll have to look up. And if you're talking about creating an array size 2 billion, that still won't work because you still have to scan the 2 billion entries in the array. Ok, technically that's O(1), but only because O(2 billion) is counted as O(1).
I actually wondered about this for a long time. If you think about it, there is no possible way even with the
HashMap. Before I get into why
HashMap doesn't work, if you don't use a
HashMap, you'll have to scan the whole size that you have to insert. Now to the
HashMap part, after inserting you're number, you'll have to update every entry after that. And if you don't, you'll get an O(1) insertion once, but after that you'll get wrong insertions.