[to11mtm]

Fair, but `n log n` definitely is the historical "good enough to actually sleep at night" in my head, every time I see it I think of the prof who taught my first CSC course and our data structures course due to how often it came up.

Also, the wise statement that 'memory is fairly cheap compared to CPU for scaling'. It's insane to see how often folks would rather manually open and scan a 'static-on-deploy' 20-100MB Json file for each request vs just parsing it into structures in memory (where, for most cases, the in memory usage is a fraction of the json itself) and just caching the parsed structure for the length of the application.

[hinkley]

Not often but occasionally I will chose the nlogn algorithm which obviously has no bugs over the O(n) algorithm with no obvious bugs.

Less brittleness is worth paying a few percent. Especially if it unmuddies the waters enough for someone to spot other accidental (time) complexity.

[refulgentis]

Considerably more than a few percent, IMHO. :)

But I also don't dabble in this area nearly enough to know whether there's years of tears and toil finding out repeatedly that O(n) is ~impossible to implement and verify :)

  | n   | n log n  |
  | 5   | 8.0472   |
  | 10  | 23.0259  |
  | 25  | 80.4719  |
  | 50  | 195.6012 |
  | 100 | 460.5170 |

[Someone]

Depends on the constants and on the value of n. If the constant for the O(n log n) algorithm is five times that of the O(n) algorithm, the O(n) algorithm is faster for n < 100.

If you expect that n < 100 will always hold, it may be better to implement the O(n) algorithm and add a logging warning if n > 250 or so (and, maybe, a fatal error if n > 1000 or so), instead of spending time to write both versions of the algorithm and spend time finding the cut off value for choosing between the two.

[hinkley]

Fatal errors tend to blow up in production rather than test.

One of the simplest solutions for detecting cyclic graphs is instead of collecting a lookup table or doing something non-concurrent like marking the nodes, is to count nodes and panic if the encountered set is more than an order of magnitude more than you expected.

I came onto a project that had done that before and it blew up during my tenure. The worst case graph size was several times the expected case, and long term customers were growing their data sets vertically rather than horizontally (eg, ever notice how much friction there is to making new web pages versus cramming more data into the existing set?) and now instead of 10x never happening it was happening every Tuesday.

I was watching the same thing play out on another project recently but it got cancelled before we hit that threshold for anything other than incorrect queries.

[refulgentis]

Just wanted to say you're one of my favorite posters. Can't put an exact reason on why, but at some point over the last 15 years I learned to recognize your name simply from consistent high quality contributions. Cheers.

[hinkley]

This is magic thinking about how C, memory hierarchies, networking, and system calls work.

[rcxdude]

It's also often in the range where constant factors can make a big difference over a wide range of n