> But when you deal with a large amount of data (I’m not talking about thousands) or if you’re fighting for milliseconds, it becomes critical to understand this concept. And guess what, databases have to deal with both situations!
I think they're just anticipating an audience who only deal with fragments of data in frontend or "backend" services. That statement holds when you're never really dealing with more than tens of elements.
Admittedly, this was a bit of an outlier case, but you get enough of those and you’re spending real money on extra hardware to keep up
Maybe you already understood that but your bug description makes it sound like complexity wasn't necessarily the issue.
Although my example was only O(n^2), the constant of each n being over the wire to the DB blew the runtime up to a significant number. So even an n-squared algorithm with small data sets can kill your app. We changed it to be O(n) over the wire to make it reasonable
A competent programmer understands that in many cases there are much faster ways of doing things with small chunks of data than asymptotically-good algorithms - and that these cases could be performance-critical if executed often.