3 ms·

The bit I glossed over is picking a random number as per sister comment. More thinking needed!

• quickthrower2 3y ago
  A cheeky way to do it is this, reuse the randomness that we are assuming about the input data: 1. Data structure in pseudo code: max = 0 items = [] def add(x: int32): max = max(x, max) items.push(x) 2. Algorithm: def doit() if max == int32.max return 0 sleep (1000) return 0 As you add items to this data structure, on average over all possible data inputs the time taken for doit() will tend from K+1000ms to a constant K.
  • daveFNbuck 3y ago
    That's what I'm saying. The runtime will go down to a constant. It can't keep decreasing forever.
    • quickthrower2 3y ago
      “Tend to” is a mathematical term mean get closer to. Formally, for any e as small as you like there exists an N within e of the value being approached. 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.
      • daveFNbuck 3y ago
        An algorithm can't have that property for its expected runtime, as it can only look at a sub-constant amount of the input of it runs in sub-constant time. 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.