Why We Drop Constants in Big O Notation
Understand the mathematical rules of Big O Notation and why coefficients and constants are ignored when analyzing algorithms.
The Rule of Dominant Terms
When you first learn to calculate time complexity, you might look at code with two consecutive loops and say, "The first loop takes N steps, and the second loop takes N steps. Therefore, the complexity is O(2N)."
Your logic is sound, but in Big O Notation, O(2N) does not exist. It is simply O(N). Why?
The Big Picture at Infinity
Big O Notation only cares about what happens when the input size (N) approaches infinity.
Imagine N is 1 Trillion.
- An O(N) algorithm takes 1 Trillion steps.
- An O(2N) algorithm takes 2 Trillion steps. Yes, one is technically twice as slow. But compared to an O(N^2) algorithm, which would take 1,000,000,000,000,000,000,000,000 steps, the difference between 1 Trillion and 2 Trillion is totally irrelevant. They both scale in a straight, linear line.
Dropping the Constants
Because scaling categories are so massive, we drop all mathematical constants and coefficients.
- O(5N) becomes O(N)
- O(N/2) becomes O(N)
- O(100) becomes O(1)
Dropping Non-Dominant Terms
What if your algorithm has a nested loop O(N^2) followed by a single loop O(N)? The exact math is O(N^2 + N). If N is 1 Million, N^2 is 1 Trillion, and N is 1 Million. 1,000,000,000,000 + 1,000,000 is basically just 1 Trillion. The N^2 completely eclipses the N. Therefore, we drop the non-dominant term. The final complexity is just O(N^2).
The Takeaway
Big O is not an exact measurement of operations; it is a categorical bucket that describes the shape of the scaling curve. Drop the coefficients, drop the smaller terms, and focus only on the largest bottleneck in your code.
Because Big O describes the overarching growth trend as data scales to infinity. A multiplier of 2 does not change the fact that the growth is linear.
In real-world milliseconds, O(N) is twice as fast. But in Big O academic notation, they belong to the exact same 'Linear' classification bucket.
It is a slower-growing term in a mathematical equation. For example, in O(N^2 + N), the N is non-dominant because as numbers get huge, N^2 completely overshadows it.
Mathematically it is O(3N), but following Big O rules, we drop the constant 3, making the final official time complexity O(N).
Yes, the exact same mathematical rules apply. Using 2 arrays of size N is O(2N) space, which simplifies to O(N) space complexity.