A constant factor is a multiplicative cost that stays fixed as input size grows. Improving it can make an algorithm much faster without changing its asymptotic complexity. section 4.2.2
A faster implementation is still linear
A naive array implementation of a cellular simulation examines every cell, making each tick O(n). A GPU implementation can run about 200× faster, but the algorithm remains linear because it still processes every cell. section 4.2.2
Constant-factor improvements can be substantial, but they have a specific limit:
- Profiling, implementation tuning, better memory use, and specialized hardware can reduce the time or space multiplier. section 4.2.2
- They do not remove the underlying growth rate when the algorithm still examines every input element. section 4.2.2
- In weighted probability calculations, multiplying by an LCM provides another constant-factor use: it preserves proportions while making later divisions integral. section 13.2
