My first big win came as an intern, when I reduced the big O complexity of an algorithm written by a (very smart) statistician for our paper to O(n^2) instead of O(n^4). This was just driven by realizing that a couple data lookups in an inner loop were themselves O(n^2).

If I recall correctly, that raised the "feasible" value of K from about 4 to about 14 on the hardware at the time, which was more than enough for our purposes. I wanted to keep optimizing, but my boss correctly reminded me that shipping the paper was more important.