Of course, the justification can be as simple as "it has to be some number and 5000 is as good as any", but that opens the door to the discussion of whether 5000 really is as good as any other number, which is often surprisingly enlightening.
The practical version of the rule is “zero, one, and out of memory”.
The data structure doesn’t care about 12,001, but your real system does.
For example, in C, integers have minimum sizes, but no maximum. We're lucky nobody ever went, "well, our PDP-11 can only go up to 2^16, so let's set the maximum there."
That's not to say it doesn't make sense to limit things after a certain point, but you'd damn well better be able to justify it, especially if you're using a recursive data structure that could absolutely grow to infinity if needed.
We don’t have any algorithms that can deal with infinity, so stop pretending like we do. And we couldn’t build one unless the universe is infinite and expansions turns out to be incorrect. So no infinity in computer data structures.
When somebody says "this algorithm is unbounded" they of course don't mean that they've changed the laws of the universe to allow for an infinite array of memory that it can work with. They just mean that if you could do that, it'd work.
As an example: `while (node) node = node->next;` (in C, where `node`'s type defines a reference to `next` of the same type) will traverse an unbounded list. It will work just as well for zero nodes, one node, a dozen nodes, a billion nodes, and so on, as the number of nodes approaches infinity. Obviously it is impossible for you to ever create a computer with an unbounded amount of memory, but computer scientists can talk about algorithms the same way mathematicians can talk about what `f(x)=x^2` at infinity.
No mathematician, with the knowledge we have now, would ever say, "It's unreasonable for us to talk about infinity. That's simply not possible, ever, now or in the future, so let's limit things at 999,999,999,999,999,999,999,999,999." We settled this debate back in the 1600s.
And the reason is that complexity theory is on shaky ground these days and needs a revision. Forty years and six orders of magnitude ago we treated a bunch of operations as constant , which is a clever fiction that is blatantly obvious now,but some of you knuckleheads continue to not look at. Most C terms are in fact stair-stepped log(n). Every time log(n) doubles and crosses a threshold, the cost of the operation doubles, and therefore is in log(n), not C. When you’re talking billions of records that distinction is already fairly obvious, and people dealing with trillions have to architect for it.
Memory access, as it turns out, is sqrt(n), not C, and with magic hardware might some day reach the cube root of n, and don’t count on it getting any better until we can bend space. With that sort of memory access a lot of O(1) algorithms perform worst than log(n) operations.
As you go into 128 bit addressing the difference between nlogn and n^3/2 * log(n)² becomes impractical. There’s a wall there, and we won’t get past it without completely different algorithms or desktop FTL technology.
The next order of magnitude of n will require a complete rewrite of that section of the code, so in practical terms the n only goes up in a new program, not the old one, and therefore the old program cannot and never will handle a thousand times more data than it was designed for.
n^3/2 * log(n)²
The time required for 1000n is 3 million times more than n. If anyone makes a computer that is 6 orders of magnitude faster than current computers, none of us here will be alive to see it.
> Forty years and six orders of magnitude ago we treated a bunch of operations as constant , which is a clever fiction that is blatantly obvious now,but some of you knuckleheads continue to not look at. Most C terms are in fact stair-stepped log(n). Every time log(n) doubles and crosses a threshold, the cost of the operation doubles, and therefore is in log(n), not C.
Memory latency hasn't really budged in 25 years and is significantly faster than it was 40 years ago.
Pointers have gotten bigger, but they're not that big compared to data and they're only one notch away from the maximum you could ever use in a single computer.
Where are we seeing these slowdowns?
> I can also guarantee that most data structures can’t even support a googol of records and never will. Some won’t ever support a quintillion records due to complexity
A B-tree will do fine.
> Memory access, as it turns out, is sqrt(n)
Not in real single computers.
And if our baseline is 1983 latency, it would take more than unrealistic amounts of circuits and size for the speed-of-light delays to drag modern tech down to equal it, let alone be worse.
I agree that actual infinity is impractical, but “zero, one, and out of memory” gives the wrong idea, because it implies you might limit things to the amount of memory currently available or available soon. "Infinity" is better at getting across the idea that your code is not allowed to bake in any limits.