1. Data structure in pseudo code:
max = 0
items = []
def add(x: int32):
max = max(x, max)
items.push(x)
def doit()
if max == int32.max return 0
sleep (1000)
return 0
This is possible because we are sampling a probability distribution. A dice is discrete but the probability of rolling a 1 as the number of sides increases tends to zero even if there is a whole “1” in a given dice.
it's not possible for it to behave differently as n increases because it doesn't have enough time to distinguish between different values of n once it's large enough.
All algorithms have a lower-bound on runtime of 1. If a sequence is decreasing and bounded below, it converges to a value [1]. If the sequence is discrete, that means it reaches exactly that limit and never deviates from it.
[1] https://en.wikipedia.org/wiki/Monotone_convergence_theorem
You can approximate the runtime with a function that decreases forever, but the actual runtime will be constant for large enough n.
What if we devise a data structure that becomes more efficient as it grows to do a certain (perhaps useless - but that is OK!) operation.
For example we have a data structure at N=0 with a million disconnected nodes and one of them being the target node.
As N increases add a node with a pointer to the target node. The algorithm to find the target node is a random search through nodes until it finds one with a pointer then halts. As N increases, time on average decreases with complexity O(1-N/(N-K)) where K=1000000