4 ms·
I'd say the exception is when `n` is under about 10, and is counting some sort of hardware constrained thing (e.g. some operation over all CAN interfaces pesent
by SAI_Peregrinus 1y ago
I'd say the exception is when `n` is under about 10, and is counting some sort of hardware constrained thing (e.g. some operation over all CAN interfaces pesent on an OBDII connector can be O(n^(2)) since n will always be between 1 and 4). If you wouldn't have to physically replace hardware for `n` to increase, you really need to avoid n^2 operations. And even then consider them carefully, perhaps explicitly failing if `n` gets too big to allow for noticing rework is needed before new hardware hits the field.
- echelon 1y ago> perhaps explicitly failing if `n` gets too big That's the problem. A lot of these quadratic time algorithms don't set limits. Even 'n!' is fine for small 'n'. Real production use cases don't have small 'n'.
- lassejansen 1y agoOr, phrased differently, if n has an upper limit, the algorithm is O(1).
- connicpu 1y agoAs long as you have tests that regularly exercise your algorithm at n=max where you would notice if they were exceptionally slow
- masklinn 1y ago> Real production use cases don't have small 'n'. Real production use cases absolutely have small n. You don't hear about them, because it's very hard for them to cause issues. Unless the use case changes and now the n is not small anymore and nobody noticed the trap.
- haiku2077 1y agoI have an app that's been running an O n^2 algorithm in "production" (free open source app used by various communities) for about half a year now. It's been fine because "n" is "number of aircraft flying in this flight simulator" - and the simulator's engine starts to fail above around 2000 anyway. So even in the worst case it's still going to run within milliseconds.