constant factor

A fixed multiplier on an algorithm's cost, such as "three steps per item", which asymptotic notation deliberately ignores.

In more detail

Two linear algorithms can differ by a constant factor of ten and both are still O(n). Dropping constants keeps the analysis about growth, which is what decides the winner at large n. For small inputs constant factors can matter more than growth rate, which is why a simple quadratic sort can beat a clever one on ten items.

Related terms

Taught in

References