Search⌘ K
AI Features

Ruminating on Constants in Big-O Notation

Explore the significance of constants in big-O notation to understand how functions compare in growth rates. This lesson clarifies why constants are essential for accurately assessing algorithm efficiency for sufficiently large inputs, helping you grasp the flexibility and usefulness of big-O in algorithm analysis.

When trying to understand the definition of the big-O notation, it is natural to ask questions regarding the constants hiddenhidden in the big-O notation.

Constants in big-O notation not unique

There are many legitimate values of nn' for which f(n)f(n) is O(g(n))O(g(n)), in the example shown below. We can use the slider to see some valid and invalid values of nn' (we show only integer values).

In fact, in general, given that f(n)f(n) is O(g(n))O(g(n)), there are infinitely many choices for the threshold value and the constant cc'.

If something is true for all values of n5n \geq 5, then it must be true for all values of n6n \geq 6, all values of n7n \geq 7, and so on. Similarly, there are infinitely many choices of cc'. If f(n)3g(n)f(n) \leq 3 g(n), then clearly f(n)4g(n)f(n) \leq 4 g(n) ...