This is a key point. The gargantuan performance difference between main memory and the CPU cache (or indeed, the existence of significant CPU caches at all) happened well after big-O was firmly established in the CS curriculum.