3 ms·

Complexity bounds do not answer the question of how fast an algorithm or a particular implementation of it is. I don't think anybody claimed that, and that was

Complexity bounds do not answer the question of how fast an algorithm or a particular implementation of it is. I don't think anybody claimed that, and that was actually not the problem here. The problem here is that the implementation exploded when passed an input Nx larger in production than what the implementation was tested with. Complexity bounds would have prevented that problem because "maybe process creating shouldn't be O(N^2)". So sure, choose an O(N^2) algorithm if its faster than an O(N) one for small enough N, there is nothing wrong with that. But don't do that if the size of the input does not depend on you (or fall back to a O(N) algo for very large inputs). People doing this is why DDoS are a thing: my O(N^3) server was very fast for 100 connections, who would have thought that someone would DDoS it with 1000 connections - yeah, who would have thought about that, 1000 connections isn't even a real DoS, but whatever.

rightbyte 8y ago
Yes I agree. What I think is misleading about the general use of O() by programmers is that it is an theoretical construct and other discountineous effects like cache misses (cache size) etc is not taken into consideration and further more the range of n:s for which each algorithm is fastest is often ignored. Some dummy numbers: T1 = 0.0000001 n^2 + n T2 = 100000000 n Would yield: O1(n^2) O2(n) Long before n is big enough for a hypothetical server running the O(n^2) algorithm to be slower than the O(n) other effects might cap it. The best way to find out is empirical testing.
- jnurmine 8y ago
  Isn't the point the order of growth...? If you double the input size, O(N) will run twice as long, whereas O(N^2) four times as long.
  - rightbyte 8y ago
    No, that's only true at the limit as n goes towards infinity. And even if you see it as a approximation of growth for big n:s, you need to know "twice what" and "four times what" and "what's a big n" to have any use from it. For the example with multiplication of 2 n-digit numbers: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm It's O(n^1.585). Need about 1000 digits before it's actually faster than "School book" O(n^2) multiplication. https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... It's O(n log n log log n). In practice faster than Karatsuba at 10,000 to 40,000 decimal digits. Then there is the newest and hottest O(n log n) version, that's not practical at all.
    - brucedawson 8y ago
      Sure, there are some cases where O() can be misleading, but those are the exceptions. You can work in software for a long time without being affected significantly by them, whereas using O(n^2) when you could use O(n) can make your code 1,000 times slower than usable, and it does this frequently. I have fixed hundreds of O(n^2) algorithms over the years, made them O(n) or O(n log(n)), and made the product dramatically better. The fact that an O(n) algorithm can sometimes be slower than an O(n^2) feels more like pedantry than useful information in this context.

rightbyte 8y ago

Yes I agree. What I think is misleading about the general use of O() by programmers is that it is an theoretical construct and other discountineous effects like cache misses (cache size) etc is not taken into consideration and further more the range of n:s for which each algorithm is fastest is often ignored. Some dummy numbers: T1 = 0.0000001 n^2 + n T2 = 100000000 n Would yield: O1(n^2) O2(n) Long before n is big enough for a hypothetical server running the O(n^2) algorithm to be slower than the O(n) other effects might cap it. The best way to find out is empirical testing.

jnurmine 8y ago
Isn't the point the order of growth...? If you double the input size, O(N) will run twice as long, whereas O(N^2) four times as long.
- rightbyte 8y ago
  No, that's only true at the limit as n goes towards infinity. And even if you see it as a approximation of growth for big n:s, you need to know "twice what" and "four times what" and "what's a big n" to have any use from it. For the example with multiplication of 2 n-digit numbers: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm It's O(n^1.585). Need about 1000 digits before it's actually faster than "School book" O(n^2) multiplication. https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... It's O(n log n log log n). In practice faster than Karatsuba at 10,000 to 40,000 decimal digits. Then there is the newest and hottest O(n log n) version, that's not practical at all.
  - brucedawson 8y ago
    Sure, there are some cases where O() can be misleading, but those are the exceptions. You can work in software for a long time without being affected significantly by them, whereas using O(n^2) when you could use O(n) can make your code 1,000 times slower than usable, and it does this frequently. I have fixed hundreds of O(n^2) algorithms over the years, made them O(n) or O(n log(n)), and made the product dramatically better. The fact that an O(n) algorithm can sometimes be slower than an O(n^2) feels more like pedantry than useful information in this context.