Rule 3 gets me into trouble with CS majors a lot

My father did some programming in Fortran and Assembly of various flavors. He was always partial to lookup tables where they could replace complicated conditionals or computations. Memory was precious in his day but it could still be worth it if your program did something repeatedly (which most do).

I actually disagree with Rule 3! While numbers are usually small being fast on small cases generally isn't as important as performing acceptably on large cases. So I prefer to take the better big-O so that it doesn't slow down unacceptably on real-world edge-case stresses. (The type of workloads that the devs often don't experience but your big customers will.) Of course there is a balance to this, the engineering time to implement both options is an important consideration. But given both algorithms are relatively easy to implement I will default to the one that is faster at large sizes even if it is slower at common sizes. I do suspect that there is an implicit assumption that "fancy" algorithms take longer and are harder to implement. But in many cases both algorithms are in the standard library and just need to be selected. If this post focused on "fancy" in terms of actual time to i…

Well it is hedged with the word "fancy". I think a charitable reading is to understand the problem domain. If N is always small then trying to minimize the big-O is just showing off and likely counterproductive in many ways. If N is large, it might be a requirement. Most people don't need FFT algorithm for multiplying large numbers, Karatsuba's algorithm is fine. But in some domains the difference does matter. Personally I usually see the opposite effect - people first reach for a too-naive approach and implement some O(n^2) algorithm where it wouldn't have even been more complex to implement something O(n) or O(n log n). And n is almost always small so it works fine, until it blows up spectacularly.