4 ms·

Yes, lots of these problems assume fantasy infinite world. Big O notation also suffers from this - it's almost useless for real world problems.

suddenlybananas 2y ago
>Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort.
- Sankozi 2y ago
  Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms.
  - suddenlybananas 2y ago
    >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.
- LegionMammal978 2y ago
  Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.
  - Al-Khwarizmi 2y ago
    Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.
virgilp 2y ago
> Big O notation also suffers from this - it's almost useless for real world problems. This is quite a bold claim. Yeah "in the real world" you often need to take into consideration the constant factors... but to go this far to say that Big O is useless? It's very useful to figure out what would likely work (or not) for your problem, given that you know the data size - I used it for exactly that, many many times.
- Sankozi 2y ago
  Let's say you have 2 algorithms. Constant time O(1) and exp time 2^n. It seems constant time is better. But in fact it runs always 42 years. While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe. Big O says how fast complexity grows, but it doesn't say what that complexity exactly is. Does something like that happens in real world? Yes, but of course not in such drastic ways.
  - qazxcvbnm 2y ago
    A very exaggerated example to use exp time… Whatever your constant, for exp time, it’s going to run for times longer than the life of the universe on probably any n > 10… Since you know, log time is practically constant
  - forrestthewoods 2y ago
    The fact that Big O notation is sometimes misleading or not helpful is not evidence that it is not generally useful. https://www.tumblr.com/accidentallyquadratic https://www.tumblr.com/accidentallyquadratic
    - qludes 2y ago
      As a concept it is pretty useful for me in a handwavy astrophysics math way because I otherwise wouldn't necessarily know how to make my naive solution fit real world constraints.
  - pyfon 2y ago
    Most of the time the constants are going to be similar. And by similar I mean < 3 orders of magnitude say. So 2^9 or adding 9 to N eats that up pretty quick.
MattPalmer1086 2y ago
You find Big O notation useless for real world problems? I find it useful to characterise algorithmic performance, e.g. O(1), O(n) O(n^2), etc. What do you find useless about it - and do you know of something that works better?
- MrBuddyCasino 2y ago
  Simpler algorithms are usually faster for small N, and N is usually small. Big O assumption is fantasy world where N is always large, and constant factors that slow down an algorithm can be ignored.
  - MattPalmer1086 2y ago
    Yeah, constant factors are not represented and often make a big real world difference. Good point.
  - coldtea 2y ago
    >Simpler algorithms are usually faster for small N, and N is usually small. This mentality is how we ended up with cpu and memory hogging Electron apps...
    - JohnKemeny 2y ago
      That's not an accurate description. For example, it is common in sorting algorithms to do an n² algorithm like bubble sort when the list to sort is small (e.g. <50), whereas when it's larger, we do an n log n algorithm like merge sort. The issue is that merge sort does recursion, which comes with some extra cost, so that an n² algorithm beats an n log n algorithm, provided n is small. It has nothing with your criticism to do.
      - Al-Khwarizmi 2y ago
        You can (and probably should) add a threshold to recursive algorithms like mergesort so that they don't end up doing recursive calls on very small arrays. For arrays smaller than the threshold, insertion is faster than bubble sort. And if you really don't want recursion for large arrays to begin with, you have heapsort or Shell sort. I don't think there is any practical case where using bubble sort makes sense, except "efficiency doesn't matter for my use case and this is the code I already have".
nottorp 2y ago
Please read accidentally quadratic from time to time...
mkleczek 2y ago
Which is evidenced everyday when optimizing database performance by creating indexes /s

suddenlybananas 2y ago

>Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort.

Sankozi 2y ago
Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms.
- suddenlybananas 2y ago
  >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.
LegionMammal978 2y ago
Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.
- Al-Khwarizmi 2y ago
  Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.

virgilp 2y ago

> Big O notation also suffers from this - it's almost useless for real world problems. This is quite a bold claim. Yeah "in the real world" you often need to take into consideration the constant factors... but to go this far to say that Big O is useless? It's very useful to figure out what would likely work (or not) for your problem, given that you know the data size - I used it for exactly that, many many times.

Sankozi 2y ago
Let's say you have 2 algorithms. Constant time O(1) and exp time 2^n. It seems constant time is better. But in fact it runs always 42 years. While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe. Big O says how fast complexity grows, but it doesn't say what that complexity exactly is. Does something like that happens in real world? Yes, but of course not in such drastic ways.
- qazxcvbnm 2y ago
  A very exaggerated example to use exp time… Whatever your constant, for exp time, it’s going to run for times longer than the life of the universe on probably any n > 10… Since you know, log time is practically constant
- forrestthewoods 2y ago
  The fact that Big O notation is sometimes misleading or not helpful is not evidence that it is not generally useful. https://www.tumblr.com/accidentallyquadratic https://www.tumblr.com/accidentallyquadratic
  - qludes 2y ago
    As a concept it is pretty useful for me in a handwavy astrophysics math way because I otherwise wouldn't necessarily know how to make my naive solution fit real world constraints.
- pyfon 2y ago
  Most of the time the constants are going to be similar. And by similar I mean < 3 orders of magnitude say. So 2^9 or adding 9 to N eats that up pretty quick.

MattPalmer1086 2y ago

You find Big O notation useless for real world problems? I find it useful to characterise algorithmic performance, e.g. O(1), O(n) O(n^2), etc. What do you find useless about it - and do you know of something that works better?

MrBuddyCasino 2y ago
Simpler algorithms are usually faster for small N, and N is usually small. Big O assumption is fantasy world where N is always large, and constant factors that slow down an algorithm can be ignored.
- MattPalmer1086 2y ago
  Yeah, constant factors are not represented and often make a big real world difference. Good point.
- coldtea 2y ago
  >Simpler algorithms are usually faster for small N, and N is usually small. This mentality is how we ended up with cpu and memory hogging Electron apps...
  - JohnKemeny 2y ago
    That's not an accurate description. For example, it is common in sorting algorithms to do an n² algorithm like bubble sort when the list to sort is small (e.g. <50), whereas when it's larger, we do an n log n algorithm like merge sort. The issue is that merge sort does recursion, which comes with some extra cost, so that an n² algorithm beats an n log n algorithm, provided n is small. It has nothing with your criticism to do.
    - Al-Khwarizmi 2y ago
      You can (and probably should) add a threshold to recursive algorithms like mergesort so that they don't end up doing recursive calls on very small arrays. For arrays smaller than the threshold, insertion is faster than bubble sort. And if you really don't want recursion for large arrays to begin with, you have heapsort or Shell sort. I don't think there is any practical case where using bubble sort makes sense, except "efficiency doesn't matter for my use case and this is the code I already have".

nottorp 2y ago

Please read accidentally quadratic from time to time...

mkleczek 2y ago

Which is evidenced everyday when optimizing database performance by creating indexes /s