The Big-O notation may seem quite obscure when you see it for the first time. A good way to intuitively understand this notation is to consider the case of a constant. Before, we can read with the formal definition that you can find on MathWorld. Quite obscure, right?

In order to understand this notation, we consider the case of a constant, for example 6, the point is to intuitively show that 6 is Big-O of 1. For this, I just need to show that a constant, c, exists such as:

f(x) ≤ c \times g(x)

Here, I can plot on Wolfram Alpha the following function, f(x) = 6:

Obviously, for the function g(x) = 1. This inequality is satisfied for every function if

c \geq 6

In this case, the set of function above f(x) = 6 are f(x) = 7, f(x) = 8, f(x) = 9, f(x) = 10 and so on… I can plot on Wolfram Alpha these functions.

So, f(x) = 6 = O(g(x) = 1) because I can found a constant, c (here, c ≥ 6), to write an expression (here, c × g(x) = c × 1) that produce a set of functions (f(x) = 6 are f(x) = 7, f(x) = 8, f(x) = 9, f(x) = 10 and so on…) that are equal or above f(x).

Now change f(x) = 6 by f(x) = 42. It is quite easy to see that 42 = O(1) because when c = 42, I write an expression (here, c × g(x) = c × 1) that produce a set of functions (f(x) = 42 are f(x) = 43, f(x) = 44, f(x) = 45, f(x) = 46 and so on…) that are equal or above f(x).

This reasoning works for any positive integer.

For other functions, you can consult this very pedagogical YouTube video: https://www.youtube.com/watch?v=JyD-LZWa7LE

You will see that:

x^3 = O(x^2) \quad \text{when } \quad x\to 0

You can graph this on Wolfram Alpha and see that x^2 (blue curve) is above x^3 (red curve) on the [-1; 1] interval. Thus, x^3 is Big-O of x^2, when x tends to 0. Another way to see this is to compute, on Wolfram Alpha, the limit of the ratio x^3/x^2 when x tends to 0. The limit is zero:

But, from 1 to infinity, you can see on Wolfram Alpha that x^2 (blue curve) is under x^3 (red curve):

Thus, x^3 is not Big-O of x^2, when x tends to infinity:

x^3 \neq O(x^2) \quad \text{when } \quad x\to + \infty

Another way to see this is to compute on Wolfram Alpha, the limit of the ratio x^3/x^2 when x tends to infinity, instead of zero.

## 1 Comment

[…] the derivative of the term inside the brackets here for the capital and here for the labor. In a previous post, I tried to give an intuitive explanation of the Big-O notation. The first-order Maclaurin […]