4 ms·

The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frus

by achr2 10y ago

The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frustrating when someone says my streamlined O(N) algo with 5 operations has the same efficiency as their O(N) algo with 20 extra function calls and operations. Big-O is not the only determining factor...

BjoernKW 10y ago
In a way Big-O notation intentionally glosses over these differences. At a large scale 5 vs 20 per instance of n doesn't matter. It might matter for practical purposes but Big-O really is about making broad distinctions.
- _greim_ 10y ago
  Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.
  - FreeFull 10y ago
    It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm
    - stouset 10y ago
      This suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.
      - FreeFull 10y ago
        One example would be multiplying large matrices together. A common algorithm used is https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm with a big-O complexity of around O(n^2.8074). https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... has a complexity of around O(n^2.375477), but the constant factors are so large it is currently never better to use it over the Strassen algorithm.
- achr2 10y ago
  I definitely agree with you, my comment was simply to show that there are a lot of people who use Big-O as a metric at a level where it shouldn't be applied.

by achr2 10y ago

BjoernKW 10y ago

In a way Big-O notation intentionally glosses over these differences. At a large scale 5 vs 20 per instance of n doesn't matter. It might matter for practical purposes but Big-O really is about making broad distinctions.

_greim_ 10y ago
Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.
- FreeFull 10y ago
  It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm
  - stouset 10y ago
    This suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.
    - FreeFull 10y ago
      One example would be multiplying large matrices together. A common algorithm used is https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm with a big-O complexity of around O(n^2.8074). https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... has a complexity of around O(n^2.375477), but the constant factors are so large it is currently never better to use it over the Strassen algorithm.
achr2 10y ago
I definitely agree with you, my comment was simply to show that there are a lot of people who use Big-O as a metric at a level where it shouldn't be applied.