Simple maths behind Big-O

Isn’t it very common to hear about the worst-case time complexity of an algorithm? Well, let’s hear the math behind that!

Let’s say we have two functions: f(x) and g(x). Big-O notation is a way to describe how fast functions grow, especially as x becomes really, really large.

Set Theory

To put it up in simple words, the notation O(g(x)) represents a family of functions that grow no faster than g(x), up to constant factors and for large enough x.

So, when we write:

$$|f(x)| \in O(g(x)) \text{ we are saying that } f(x) \text{ belongs to this family, such that } $$

$$f(x) \text{ doesn’t outgrow } g(x) \text{ as } x \to \infty$$

Calculus

Now let’s back that up with some actual math.

We say f(x) ∈ O(g(x)) if there exist positive constants C and x₀ such that:

$$|f(x)| ≤ C\cdot|g(x)| \text{ for all } x > x_0$$

Or, in terms of limits:

$$\lim_{x \to \infty} \frac{|f(x)|}{|g(x)|} < \infty$$

This tells us that the ratio of f(x) to g(x) stays bounded. In other words, f(x) may grow, but it’s never going to grow faster than some constant multiple of g(x) beyond a certain point. For sufficiently large values of x, f(x) will always be smaller than g(x).

Example

Let us use the following example to understand it better:

$$\text{Prove that: } 2^{n} \text{ is upper bounded by } e^n \text{ i.e. } 2^n \in O(e^n)$$

Let us test with the limit, as n → infinity,

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{2^n}{e^n} = \lim_{n \to \infty} (\frac{2}{e})^n [\text{ By power of quotient rule}]$$

$$\text{ Since } e\sim2.718 > 2 \text{, therefore, } \frac{2}{e} < 1. \text{ Therefore as } n \to \infty \text{ , } ({\frac{2}{e}})^n \to 0$$

$$ \text{Therefore, } \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 < \infty. \text{ Hence, } 2^n \in O(e^n)$$

From this, it becomes clear that 2^n belongs to the set O(e^n), which means it is one of the functions in the family of functions that do not grow faster than e^n as n → infinity.

Conclusion

That’s all Big-O is: a mathematical way to group functions into families based on their long-term growth rates. It gives us a high-level idea of performance, complexity, or behaviour—without sweating the exact details. Similarly, you can later explore Big-Omega and Big-Theta to complete the picture!