points by narnarpapadaddy 2 days ago | 0 comments
Most undergrad CS students go through an algorithms course and understand a bubble sort is inherently slower than a quick sort, no amount of optimization will get you past the fundamental n^2 time complexity. You can generalize those same analysis principles to whole architectures and distributed systems. If you don’t recognize that the server interactions your solution requires boils down to an n^2 algorithm, you’re in for a bad time. Unlike a function a live, deployed system is typically harder to evolve. Sometimes constraints like backwards compatibility are such that you simply can’t fix it.
That sounds about right, a DS&A course which introduces Hoare's Quicksort, which is old enough to draw a pension, as if that's the state of the art.
Introspective sorting is more than a quarter of a century old and yet probably most people with a CS degree do not even know it exists. What a poor excuse for an engineering discipline this is.
Their big-O studies will lead them to conclude, as a Fortran textbook I've studied did almost forty years ago, that Heapsort is the right choice. Same big-O best case as Quicksort, easier to write but a better worst case. Of course the Fortran textbook does have the heart to mention that Heapsort is actually noticeably slower - but same big-O as if that's what your users will care about.
With a following wind and enough free time (or if they ask an LLM) they might come up with introspective sorting, putting them only a few decades behind the state of the art. Amazing.