9 ms·

This is an aside. But I twigged on a caption for one of the figures: “Every computational problem takes longer to solve as its input grows larger, but not all p

This is an aside. But I twigged on a caption for one of the figures: “Every computational problem takes longer to solve as its input grows larger, but not all problems grow harder at the same rate.” It’s obvious from CS201 that this phrase is generally true and I have no pedantic objection to its inclusion in the article. However, I’m curious if this is strictly true or if we can find a (nontrivial) counterexample. Are there any algorithms that run faster as input grows? My first intuition is some kind of probabilistic question solved to a given correctness bound. Edit: it is trivial to construct an algorithm with this property. My precise question is whether any meaningful problems have optimal algorithms with this property.

Q6T46nT668w6i3m 3y ago
Of course. The obvious examples are probabilistic, e.g., Monte Carlo methods, as an increase in the problem space decreases the number of samples needed.
Filligree 3y ago
I could imagine some behaviour along those lines in search engines, specifically if you're searching for similar documents. Which none of them seem to — would be useful! Let me know if I'm wrong! — but imagine a search engine that lets you look for documents 'similar to this document here'. Also imagine that's threshold-based; you want equal levels of similarity regardless of the rarity of the input document. In that case, as the size of the corpus grows it should get easier to find ones in the right range of similarity.
downWidOutaFite 3y ago
caches? the more input the fewer cache misses
mjcohen 3y ago
Depends what you mean by larger. The example that occurs to me is the priblem of determining whether or not an integer is prime. This can be done relatively quickly for numbers of the form 2^p-1 where p is prime, but would take much longer for a much smaller prime not of this form.
- Nevermark 3y ago
  Those would be effectively different problems. Adding the constraint of only needing to classify a particular form of prime will always result in an algorithm of equal or lesser complexity order.
dilawar 3y ago
Finding a set of mututally orthogonal vectors. For a given sparsity, after a large enough dimention, two randomly chosen vector will almost always be orthogonal.
- Nevermark 3y ago
  That would be a case of higher probability of finding a solution in one step. But the solution would still need to be checked and another candidates generated until a solution is found. Average time would be minimized by generating random vectors each time. But that would increase the worst case to unbounded (effectively infinite) time since an increasingly vanishingly small but finite chance that a solution has not yet been found will exist after any number of steps. Some kind of simple search would be vastly more bounded, but in practice require more computation.
krackers 3y ago
If you are willing to settle for expected instead of worst case time, there are many string-related algorithms that are O(m/n). Intuition is that as the string size grows it's "more likely" to have some property on expectation.
- PartiallyTyped 3y ago
  Same for hash related algorithms and data structures.
daveFNbuck 3y ago
> 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.
paulddraper 3y ago
> it is trivial to construct an algorithm with this property Actually, it is impossible to construct an algorithm with this property, at least under any usual computational model. Every computational model has discrete time units; therefore the amount of time taken cannot be vanishingly small. (This is assuming the usual notion of complexity, where only the asymptotic behavior matters. It doesn't matter if it gets increasingly faster over the first million input sizes...it only matters what the behavior is as n -> infinity.) A program cannot be increasingly faster forever.
- Dylan16807 3y ago
  "Faster as the input grows" is perfectly compatible with a minimum number of time units. If your definition insists the minimum of time units must be 0, with infinitesimal time getting involved, then your definition sucks.
  - paulddraper 3y ago
    For a function to strictly decrease forever, at least one of two statements is true: 1. It decreases by vanishingly smaller amount. 2. It decreases to negative infinity. So...which is it? Infinitesimal time units, or negative time?
    - quickthrower2 3y ago
      Strictly speaking it either tends to negative infinity, or tends to so real number X, which could be any number positive or negative.
      - paulddraper 3y ago
        In that latter case, statement 1 is true.
    - Dylan16807 3y ago
      3. Nobody said "strictly".
nullc 3y ago
If your computational model requires that the algorithm reads the input then I don't see how it's possible. Even if above some size the algorithm does nothing but exits the time will still grow linearly with the input from reading. You could imagine an algorithm that takes some astronomical time for size 1, less for 2, etc.. but for any finite time at size 1 there will be some size N where the reading time finally dominates the computation.

Q6T46nT668w6i3m 3y ago

Of course. The obvious examples are probabilistic, e.g., Monte Carlo methods, as an increase in the problem space decreases the number of samples needed.

Filligree 3y ago

I could imagine some behaviour along those lines in search engines, specifically if you're searching for similar documents. Which none of them seem to — would be useful! Let me know if I'm wrong! — but imagine a search engine that lets you look for documents 'similar to this document here'. Also imagine that's threshold-based; you want equal levels of similarity regardless of the rarity of the input document. In that case, as the size of the corpus grows it should get easier to find ones in the right range of similarity.

downWidOutaFite 3y ago

caches? the more input the fewer cache misses

mjcohen 3y ago

Depends what you mean by larger. The example that occurs to me is the priblem of determining whether or not an integer is prime. This can be done relatively quickly for numbers of the form 2^p-1 where p is prime, but would take much longer for a much smaller prime not of this form.

Nevermark 3y ago
Those would be effectively different problems. Adding the constraint of only needing to classify a particular form of prime will always result in an algorithm of equal or lesser complexity order.

dilawar 3y ago

Finding a set of mututally orthogonal vectors. For a given sparsity, after a large enough dimention, two randomly chosen vector will almost always be orthogonal.

Nevermark 3y ago
That would be a case of higher probability of finding a solution in one step. But the solution would still need to be checked and another candidates generated until a solution is found. Average time would be minimized by generating random vectors each time. But that would increase the worst case to unbounded (effectively infinite) time since an increasingly vanishingly small but finite chance that a solution has not yet been found will exist after any number of steps. Some kind of simple search would be vastly more bounded, but in practice require more computation.

krackers 3y ago

If you are willing to settle for expected instead of worst case time, there are many string-related algorithms that are O(m/n). Intuition is that as the string size grows it's "more likely" to have some property on expectation.

PartiallyTyped 3y ago
Same for hash related algorithms and data structures.

daveFNbuck 3y ago

> 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.

paulddraper 3y ago

> it is trivial to construct an algorithm with this property Actually, it is impossible to construct an algorithm with this property, at least under any usual computational model. Every computational model has discrete time units; therefore the amount of time taken cannot be vanishingly small. (This is assuming the usual notion of complexity, where only the asymptotic behavior matters. It doesn't matter if it gets increasingly faster over the first million input sizes...it only matters what the behavior is as n -> infinity.) A program cannot be increasingly faster forever.

Dylan16807 3y ago
"Faster as the input grows" is perfectly compatible with a minimum number of time units. If your definition insists the minimum of time units must be 0, with infinitesimal time getting involved, then your definition sucks.
- paulddraper 3y ago
  For a function to strictly decrease forever, at least one of two statements is true: 1. It decreases by vanishingly smaller amount. 2. It decreases to negative infinity. So...which is it? Infinitesimal time units, or negative time?
  - quickthrower2 3y ago
    Strictly speaking it either tends to negative infinity, or tends to so real number X, which could be any number positive or negative.
    - paulddraper 3y ago
      In that latter case, statement 1 is true.
  - Dylan16807 3y ago
    3. Nobody said "strictly".

nullc 3y ago

If your computational model requires that the algorithm reads the input then I don't see how it's possible. Even if above some size the algorithm does nothing but exits the time will still grow linearly with the input from reading. You could imagine an algorithm that takes some astronomical time for size 1, less for 2, etc.. but for any finite time at size 1 there will be some size N where the reading time finally dominates the computation.