Accidentally Quadratic

For me, I think the problem is that normal, boring, stupid, unsophisticated, plebian imperative programming lives in a world of O(1) operations. That is to say, a "normal" line of code you type will be O(1), and then you generally start gluing those together with various things that start stacking on O(n) complexities. As things like the accidentally quadratic blog [1], in the normal programming world it is a bit humorous to even so much as accidentally stack two of those things unnecessarily on top of each other.

Certainly, people manage to make poorly performing things even so, but at least at the base level, your primitives may be stupid, but they are generally fast.

The logic programming world works in a default space of O(n) operations, that stack together more freely than the imperative world, and that gives easy access to O(2^n). Since this is essentially impossible, a great deal of work is done to try to get that down, but you're always intrinsically starting behind the eight-ball. It is easier to work up from O(1) operations than to write an exponential or super-exponential algorithm and then try to trim it back down to a decent complexity for a normal programmer.

I think this is the root cause as to why logic programming is generally not something we see a lot of. It's like a wild stallion; it may be powerful but the amount of effort you pour into just keeping it under control may exceed any benefit you could get.

It isn't useless, of course. Amazing work has…

> The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant.

Accidentally quadratic is such a thing there's a blog[1], and it's regularly the source of problems of a certain blogger who debugs problems in Windows that are usually causing his "stupidly fast" hardware to run bog slow[2].

Just this week, I hit what seems to be an accidentally-quadratic bug in macOS's tail — tail! I'm not even sure how you write an accidental O(n²) in implementing tail, but yet macOS tail takes 7 minutes to process a log file on my system that GNU tail can process in 80 milliseconds.

Regex regularly lead to oops-O(n²) due to devs not grokking the greedy nature of the star character, and for a while last year it felt like every week some NPM package was getting a security vuln. for a DoS vuln. due to quadratic regexes.

Understanding how B-Trees work — and more importantly, when they don't — in database queries is a perennial source of bugs in every company I've worked at where queries get written that won't hit an index, and don't get noticed until they're hitting production levels of rows. Dev confusion entails — "but the index has the columns I'm querying!" … yes, but that's not how a B-Tree works.

And it's not just the order-notation. I've seen, numerous times, people re-discover topological sort, or worse, hack a solution onto a problem where the problem is a DAG, and the solution is topo-sort, but instead you get…

Asking if the list is sorted was also the very first question that popped up in my head, because it makes the difference between a linear and a quadratic algorithm. Contrary to, for example, having the choice between an n log n algorithm and a linear algorithm, when given the choice between a quadratic and a linear algorithm, it is very rare that the right choice is the quadratic algorithm. (Semi-related: [1])

(EDIT: after thinking about this more than two seconds, the quadratic algorithm for unsorted input can become n log n by sorting the list, though that takes linear space. This would certainly be a clarifying question.)

The other questions would be less obvious to me, though I'd encounter them while thinking more than 2 seconds about the problem, I suppose.

Or maybe this just outs me as an ex-amateur competitive programmer :)

[1]: https://accidentallyquadratic.tumblr.com/

Bottom up dynamic programming algorithms require some cleverness.

All of the ones listed can be solved with a top down dynamic programing algorithm. Which just means "write recursive solution, add caching to memoize it".

For some of these, you can get cleverer. For example the coin change problem is better solved with an A* search.

Still, very few programmers will actually need these algorithms. The top thing we need is to recognize when we accidentally wrote a quadratic algorithm. A quick scan of https://accidentallyquadratic.tumblr.com/ shows that even good people on prominent projects make that mistake on a constant basis. So apparently being able to produce an algorithm on the test, doesn't translate to catching an algorithmic mistake in the wild.