Constants in Big O Notation

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store