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
- Big O notation — A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
- asymptotic analysis — Studying how an algorithm's cost behaves as the input size grows very large, ignoring constant factors and small inputs.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers