Constants in Big O Notation

Constants in big O notations are usually ignored because they don’t add much to the complexity when the input size is very large. But, they do have significant meaning when the input is small or when we want to make a comparison between different algorithms. Let’s discuss these two scenarios in this short-but-somewhat-useful treatise.

In my previous write-up, Big O Notation, I tried to present big O notations in a fathomable way. When we determine O( ) for an algorithm, we tend to ignore constants since when the input is very large, these constants don’t matter much.

Constants matter for the following cases:

Small Input Size:

Comparing Two Algorithms Having Similar Time Complexity:

Since we are more concerned about determining a relationship between runtime and input size, constants don’t make contributory meaning to this relationship. Say, T(n) = n + 7 and T(n) = n + 70000 both have a linear nature between T(n) and n. We can say both have O(n). However, this difference is not insignificant at all when we want to know which algorithm is faster.

Comparing Two Algorithms Having Different Time Complexities:

Now, if two algorithms have different O( )- one is of O(n²) and the other one is of O(n)- and thus different equations for T(n)- T(n) = n²/10 and T(n) = 100n, respectively, then T(n) = n²/10 is faster than T(n) = 100n up to a certain value of n. After this threshold of n, T(n) = n²/10 is always slower than T(n) = 100n. This is the reason O( ) has a condition (n≥ nₒ) in its definition.

To sum up, constants are considered for these afore-discussed three cases (there might be more, but this is what I am aware of as of writing this). There’s more to it but let’s keep that for a different write-up. I have read multiple articles on the internet regarding Big O and I am grateful to every one of them. Now, passing on to you geniuses. Stay safe and nerdiest.

Science-savvy