If I have an algorithm A. and it has fewer instructions than algorithm B. but performs worse on a CPU due to poor memory coalescing (and hence, poor CPU cache performance), does that factor into the Time Complexity analysis - given that, CPUs can have different wildly different cache implementations (or no cache) such that a algorithm's effectiveness can only be adequately judged on a single given CPU?If you don't understand the issue in question, please watch Mike Acton's CPPCon speech on youtube (Data Oriented Design).
Does Time Complexity analysis factor for cache performance of an algorithm?
c++;memory;complexity;time
Time Complexity (Big-O notation) does not measure performance of an algorithm. Instead, it categorizes how an algorithm's resource use scales with input size. This allows us to compare two algorithms with a judgement such as for some sufficiently big input, algorithm A will always be faster than algorithm B. We can do this judgement without even considering concrete implementations of the algorithms. As such, Big-O is not concerned about implementation details such as caching.However, we do assume certain implementation details when calculating Big-O. E.g. it is common to assume that each memory access has constant cost. This clearly does not hold in an environment where lookups are actually O(n) (e.g. when memory is represented as a linked list). If you want to be very precise when calculating Big-O, we must draw up a cost model that assigns a concrete cost for each operation, though this may be expressed in terms of some undetermined constants. E.g. we usually assume that a memory load has concrete running time T(n) = c for some constant c. This constant will be eliminated when simplifying to Big-O. Incidentally, caching does not change the constant-time guarantee  as long as there is some fixed upper bound for an operation, it can be considered constant. Here, this would be the cost of a read with cache miss.This also means that Big-O is not suitable for comparing real-world performance of algorithms with known workloads. Two algorithms might be in the same complexity class, but one may outperform the other by a consistent factor of 1000. Or one algorithm might have spectacular linear complexity, but requires so much pre-processing that even an exponential algorithm is faster in practice (real example: many regex engines).