# 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.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1746468075402/c78324b5-df91-409b-815a-2d5ef3f4014c.png align="center")

## 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!