# Understanding this explanation about Big O notation

I'm trying to learn the Big O Notation...and I got a bit confused by this article:

https://brilliant.org/practice/big-o-notation-2/?chapter=intro-to-algorithms&pane=1838

where it stands that f(x) = 4x and g(x) = 10x, (...), and that one could look at the Big O Notation by dividing f(x) by g(x): 10x/4x

Shouldn't it be 4x/10x instead in this very example? (since f(x) = 4x and g(x) = 10x) Or is just me who got it all wrong?...

Kind regards,

c

The best way to look at big $O$ notation is the following: $f(x)$ and $g(x)$ have the same $O$ complexity if you can find a positive constants $c_1, c_2 \in \mathbb{R}$ such that $f(x) \leq c_1 \cdot g(x)$ and $g(x) \leq c_2 \cdot f(x)$ for all $x$.

So, for example $4x$ and $10x$ are both in the same complexity class because $4x \leq 1 \cdot 10x$ and $10x \leq 3 \cdot 4x$. We name the complexity class they belong to $O(x)$, because $x$ is the simplest of all expressions of the form $c \cdot x$ so we use it as a representative.

Also, one can write equalities with big $O$; $$O(4x) = O(10x) = O(x) = O(192839182x) \neq O(x^2)$$

Some basic complexity classes are (in order of complexity, from lower to higher):

• $O(log n)$
• $O(n)$
• $O(n log n)$
• $O(n^2)$
• $\ldots$
• $O(n^k)$
• $\ldots$
• $O(2^n)$
• $\ldots$

and every complexity class on this list is not equal to any other.

• This is basically right but please don't confuse complexity classes and orders of growth. A complexity class is a class of computational problems, based on some kind of resource usage; $O(...)$ is a class of mathematical functions. There are no complexity classes in your answer because you're talking only about the growth rate of mathematical functions. – David Richerby Aug 20 '18 at 22:46
• Not for all $x$, it is enough if it is valid for $x$ large enough (we are interested in the functions for "very large" values of $x$, for suitable "very large"). – vonbrand Mar 3 '20 at 16:17