TIL Advent of Code and Project Euler will deliberately look for puzzles where the naive solution is worse than quadratic.
This ensures that people can solve them with any programming language. You don't want fast languages to be able to use the naive solution.
miniblog.
Related Posts
One nice thing about quadratic algorithms: if you can reduce your N, you get a really nice speedup.
It makes sense to worry about writing code that is accidentally quadratic.
Turns out you don't need to worry about accidentally exponential code. It's painfully obvious.
Robin Hood hashing, and a remarkable bug in Rust where building one hash map from another can have quadratic performance!
https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion