Hacker News new | ask | show | jobs
by ashishb 376 days ago
O(n^2) is fast enough to end up I'm production and slow enough to cause problems at scale.

The worst troublesome cases of inefficient production are almost always O(n^2).

1 comments

Had a modular monorepo back when UML was still a thing people did. People were having trouble opening a TogetherJ project - it was taking 30 minutes. I dug into it, and I don’t recall how I timed it but I kept adding more submodules and the runtime went up ridiculously fast. I stopped at a project that took 18 hours to load. Started it before going home one day and timed it the next morning.

When I plotted the runtime, I got n^5 for the fitting curve. That’s the largest polynomial I’ve encountered in the wild. Second place has always been cubic.

Their response was that it had something to do with processing config files per module, and a suggestion to rearrange them as a workaround. They fixed the problem in the next patch and the load time went from 18 hours to a couple minutes.