**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

Last modified: November 3, 2018

In this article, we’ll give an **introduction to the mathematics of big-O notation, as well as show an example of a big-O proof.**

**Definition:** *f(x) = O(g(x))* means that there exist two positive constants, *x _{1}* and

When saying *f(x) = O(g(x))*, we say** “ f of x is big-O g of x“.**

Don’t let the equals sign fool you: *f(x)* is a function and *O(g(x))* is a set. You can’t have a function equalling a set. That’s like saying that the Earth equals the Solar System. It’s more like, the Earth *belongs* in (the set of planets which comprise) the Solar System. Similarly, ** f(x) belongs in a set of functions called O(g(x))** (

We have two functions now – *f(x)* and *g(x)*. Functions grow at different speeds. For example, a quadratic function will grow quicker than a linear function. But **sometimes, it takes some time for the quadratic to catch up! **

For example, if we have *a(x) = 2x ^{2} + 2x + 1* and

Importantly for the case of understanding big-O formally, **we don’t particularly care at which point a(x) began outgrowing b(x).** Just that it did, and that from that point onwards, it continues to be larger than

We saw above how it took a while for *a(x)* to catch up to *b(x). *Eventually, it did, but it took a while.

The reason it eventually grows faster is because of the *2x ^{2} *term. Or, more precisely, the

For big-O, we don’t care about the other terms in *a(x)*, or the constant *2* in the *2x ^{2}* term.

Looking again at our definition from section 2, this is where the constant *c* comes in. **We can scale g(x) by any positive constant** – as long as

If we take *d(x) = 3x ^{3} + 2x + 10,* we’ll need to find values of

In order to prove *f(x) = O(g(x))*, we need to find two positive constants, *c* and *x _{1}*, such that

What it means, is that past a certain point, a scaled version of *g(x)* will always be bigger than *f(x)*.

Let d*(x) = 3x ^{3} + 2x + 10*.

Suppose we wish to prove that d*(x) = O(x ^{3})*. This means we need to find two positive integers,

Well, we know that

d*(x) = 3x ^{3} + 2x + 10 ≤ 3x^{3} + 2x^{3} + 10x^{3} = 15x^{3}*

so,

*d(x) ≤ 15x ^{3}*.

So if we set *x _{1} = 1 *and

We could have found other values for *x _{1}* and

In this article, we focused on an **introduction to the theory of big-O notation**.

A more practical look at this topic can be found here.