7 ms·

Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into produc

Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6st7nc2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

paulddraper 1y ago
The second law is that O(n * log n) is for practical intents and purposes O(n).
- EdwardCoffin 1y ago
  To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6stamk2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
  - to11mtm 1y ago
    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 1y ago
      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 1y ago
        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 |
        hinkley 1y ago
        This is magic thinking about how C, memory hierarchies, networking, and system calls work.
        Someone 1y ago
        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 1y ago
        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.
    - deleted 1y ago
      [deleted]
    - rcxdude 1y ago
      It's also often in the range where constant factors can make a big difference over a wide range of n
  - paulddraper 1y ago
    Yes, that isn't actually Dawson's second law.
  - brucedawson 1y ago
    Should it be my second law? https://bsky.app/profile/randomascii.bsky.social/post/3lr24sdjlc22k https://bsky.app/profile/randomascii.bsky.social/post/3lr24s...
- hinkley 1y ago
  But sometimes a big enough C can flip which solution helps you hit your margins.
  - hansvm 1y ago
    In my mind, that's always been the point in dropping log factors. The algorithms are comparable enough that the actual implementation starts to matter, which is all we're really looking for in a Big-O analysis.
- sn9 1y ago
  Skiena has a great table in his algorithms book mapping time complexity to hypothetical times for different input sizes. For n of 10^9, where lgn takes 0.03 us and n takes 1 s, nlgn takes 29.9 s and n^2 takes 31.7 years.
  - swyx 1y ago
    more from table please?
    - johnisgood 1y ago
      I would rather have the table and related content. Name of the book?
      - EdwardCoffin 1y ago
        It's probably The Algorithm Design Manual 2ed by Steven S. Skiena, figure 2.4 The second table on this [1] page is pretty similar, though not the same. [1] https://a1120.cs.aalto.fi/notes/round-efficiency--bigoh.html https://a1120.cs.aalto.fi/notes/round-efficiency--bigoh.html
hinkley 1y ago
I made the “mistake” in an interview of equating two super-quadratic solutions in an interview. What I meant was what Dawson meant. It doesn’t matter because they’re both too ridiculous to even discuss.
- dieortin 1y ago
  They’re too ridiculous… unless a more optimal solution does not exist
  - hinkley 1y ago
    Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can only do it badly with no hope of ever correcting it, you should outsource it.
    - Retric 1y ago
      Chess engines faced worse than quadratic scaling and came out the other side… Software operates in a crazy number of different domains with wildly different constraints.
      - crabmusket 1y ago
        I believe hinkley was commenting on things that are quadratic in the number of users. It doesn't sound like a chess engine would have that property.
        tux3 1y ago
        They did make it sound like almost anything would necessarily have n scale with new users. That assumption is already questionnable There's a bit of a "What Computational Complexity Taught Me About B2B SaaS" bias going.

paulddraper 1y ago

The second law is that O(n * log n) is for practical intents and purposes O(n).

EdwardCoffin 1y ago
To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6stamk2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
- to11mtm 1y ago
  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 1y ago
    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 1y ago
      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 |
      - hinkley 1y ago
        This is magic thinking about how C, memory hierarchies, networking, and system calls work.
      - Someone 1y ago
        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 1y ago
        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.
  - deleted 1y ago
    [deleted]
  - rcxdude 1y ago
    It's also often in the range where constant factors can make a big difference over a wide range of n
- paulddraper 1y ago
  Yes, that isn't actually Dawson's second law.
- brucedawson 1y ago
  Should it be my second law? https://bsky.app/profile/randomascii.bsky.social/post/3lr24sdjlc22k https://bsky.app/profile/randomascii.bsky.social/post/3lr24s...
hinkley 1y ago
But sometimes a big enough C can flip which solution helps you hit your margins.
- hansvm 1y ago
  In my mind, that's always been the point in dropping log factors. The algorithms are comparable enough that the actual implementation starts to matter, which is all we're really looking for in a Big-O analysis.
sn9 1y ago
Skiena has a great table in his algorithms book mapping time complexity to hypothetical times for different input sizes. For n of 10^9, where lgn takes 0.03 us and n takes 1 s, nlgn takes 29.9 s and n^2 takes 31.7 years.
- swyx 1y ago
  more from table please?
  - johnisgood 1y ago
    I would rather have the table and related content. Name of the book?
    - EdwardCoffin 1y ago
      It's probably The Algorithm Design Manual 2ed by Steven S. Skiena, figure 2.4 The second table on this [1] page is pretty similar, though not the same. [1] https://a1120.cs.aalto.fi/notes/round-efficiency--bigoh.html https://a1120.cs.aalto.fi/notes/round-efficiency--bigoh.html

hinkley 1y ago

I made the “mistake” in an interview of equating two super-quadratic solutions in an interview. What I meant was what Dawson meant. It doesn’t matter because they’re both too ridiculous to even discuss.

dieortin 1y ago
They’re too ridiculous… unless a more optimal solution does not exist
- hinkley 1y ago
  Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can only do it badly with no hope of ever correcting it, you should outsource it.
  - Retric 1y ago
    Chess engines faced worse than quadratic scaling and came out the other side… Software operates in a crazy number of different domains with wildly different constraints.
    - crabmusket 1y ago
      I believe hinkley was commenting on things that are quadratic in the number of users. It doesn't sound like a chess engine would have that property.
      - tux3 1y ago
        They did make it sound like almost anything would necessarily have n scale with new users. That assumption is already questionnable There's a bit of a "What Computational Complexity Taught Me About B2B SaaS" bias going.