6 ms·

> Edit: it is trivial to construct an algorithm with this property. It's actually impossible to construct an algorithm that has its runtime decrease as the in

> Edit: it is trivial to construct an algorithm with this property. It's actually impossible to construct an algorithm that has its runtime decrease as the input size grows. You can do this for finitely many examples, but we're talking about asymptotics here. With discrete run-times and a lower-bound of 1 operation, the run-time will have to stop decreasing at some point and just stay at the same constant value for all but finitely-many exceptions. This makes it a constant-time algorithm. A constant run-time is a counter-example to that caption though, as the problem doesn't take longer as the input grows. An example would be checking if a number is divisible by 2. You only need to check 1 bit, so it doesn't take any longer as you add more bits that the algorithm doesn't touch.

Dylan16807 3y ago
You could use just the asymptote and call it "constant time". But that's an extremely limited and misleading analysis, so you should not do that. If the time taken goes from a quadrillion to 7 as the problem size grows, don't call it constant.
- qbit42 3y ago
  You do if you are a complexity theorist :)
- daveFNbuck 3y ago
  "constant time" in complexity theory just means there's a constant bound on runtime. It doesn't have to actually have the exact same runtime down to the instruction for every input. Here, the bound would be a quadrillion. Of course, showing a constant upper-bound doesn't tell us that it isn't even faster than constant as in the proposition I was responding to. That's why I focused on the constant lower-bound.
  - Dylan16807 3y ago
    I know what it means, and I stand by it being limited to the point of misleading in a case like this. Running any (halting) algorithm on a human computer is constant time, because you're bound by the number of states you can fit into some terabytes, but nobody should actually try to use that as a final analysis.
    - daveFNbuck 3y ago
      > Running any (halting) algorithm on a human computer is constant time, because you're bound by the number of states you can fit into some terabytes, but nobody should actually try to use that as a final analysis. That's the sort of thing I would usually say to explain why we do things like use asymptomatic analysis and ignore polynomial factors. If you have a different solution, that's great, but you're no longer taking about the kind of runtime the article is about.
      - Dylan16807 3y ago
        It depends on how abstract you want to be. You shouldn't always shove the lever all the way to the most abstract single value. My suggested solution is "don't delete all nuance". If the runtime doesn't behave nicely, give that a mention. Most things do behave nicely, so that's not much of a burden. > the kind of runtime the article is about The article spends plenty of time talking about computational feasibility, which is not about the limits as you approach infinity. It even equates P with "trivial", which is... not good.
lacker 3y ago
I guess even if you allow probabilistic algorithms and expected runtime, you still can't have an algorithm that runs faster as the input size grows. Because... it takes O(log n) time to calculate any random variable whose expected value has a denominator of size n? I'm not entirely sure but that seems right to me.
- Dylan16807 3y ago
  That's for randomly sampling a large input? If each piece of input is already independent, then you don't have to calculate that, you can just use the input in order.
- daveFNbuck 3y ago
  With probabilistic algorithms, you still have the fundamental limitation that there's a lower-bound to how fast an algorithm can run. You can't keep getting faster indefinitely.
  - lacker 3y ago
    You could get faster in expected value. What if the time on input of length n was an expected value of 100 + 1/n? That isn't possible, but it might not quite be obvious why that isn't possible.
    - daveFNbuck 3y ago
      Having a constant runtime means there's a constant bound on the runtime, not that the runtime is an exact constant value. 100 + 1/n would still be constant, as it's bounded above and below by constants. To have sub-constant time it would have to go to 0 as n increases, as otherwise we could bound the time below by a constant. This isn't possible, as a computer will take at least 1 time unit on every input. So the expected time will always be at least 1.
quickthrower2 3y ago
Maybe not! With O(log N) such as binary search you are assuming some sort of structure to the data. It is not necessary for an algorithm to scan (otherwise O(N) is as good as it would get) 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
- quickthrower2 3y ago
  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.

Dylan16807 3y ago

You could use just the asymptote and call it "constant time". But that's an extremely limited and misleading analysis, so you should not do that. If the time taken goes from a quadrillion to 7 as the problem size grows, don't call it constant.

qbit42 3y ago
You do if you are a complexity theorist :)
daveFNbuck 3y ago
"constant time" in complexity theory just means there's a constant bound on runtime. It doesn't have to actually have the exact same runtime down to the instruction for every input. Here, the bound would be a quadrillion. Of course, showing a constant upper-bound doesn't tell us that it isn't even faster than constant as in the proposition I was responding to. That's why I focused on the constant lower-bound.
- Dylan16807 3y ago
  I know what it means, and I stand by it being limited to the point of misleading in a case like this. Running any (halting) algorithm on a human computer is constant time, because you're bound by the number of states you can fit into some terabytes, but nobody should actually try to use that as a final analysis.
  - daveFNbuck 3y ago
    > Running any (halting) algorithm on a human computer is constant time, because you're bound by the number of states you can fit into some terabytes, but nobody should actually try to use that as a final analysis. That's the sort of thing I would usually say to explain why we do things like use asymptomatic analysis and ignore polynomial factors. If you have a different solution, that's great, but you're no longer taking about the kind of runtime the article is about.
    - Dylan16807 3y ago
      It depends on how abstract you want to be. You shouldn't always shove the lever all the way to the most abstract single value. My suggested solution is "don't delete all nuance". If the runtime doesn't behave nicely, give that a mention. Most things do behave nicely, so that's not much of a burden. > the kind of runtime the article is about The article spends plenty of time talking about computational feasibility, which is not about the limits as you approach infinity. It even equates P with "trivial", which is... not good.

lacker 3y ago

I guess even if you allow probabilistic algorithms and expected runtime, you still can't have an algorithm that runs faster as the input size grows. Because... it takes O(log n) time to calculate any random variable whose expected value has a denominator of size n? I'm not entirely sure but that seems right to me.

Dylan16807 3y ago
That's for randomly sampling a large input? If each piece of input is already independent, then you don't have to calculate that, you can just use the input in order.
daveFNbuck 3y ago
With probabilistic algorithms, you still have the fundamental limitation that there's a lower-bound to how fast an algorithm can run. You can't keep getting faster indefinitely.
- lacker 3y ago
  You could get faster in expected value. What if the time on input of length n was an expected value of 100 + 1/n? That isn't possible, but it might not quite be obvious why that isn't possible.
  - daveFNbuck 3y ago
    Having a constant runtime means there's a constant bound on the runtime, not that the runtime is an exact constant value. 100 + 1/n would still be constant, as it's bounded above and below by constants. To have sub-constant time it would have to go to 0 as n increases, as otherwise we could bound the time below by a constant. This isn't possible, as a computer will take at least 1 time unit on every input. So the expected time will always be at least 1.

quickthrower2 3y ago

Maybe not! With O(log N) such as binary search you are assuming some sort of structure to the data. It is not necessary for an algorithm to scan (otherwise O(N) is as good as it would get) 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

quickthrower2 3y ago
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.