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


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,



1 Answer 1


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.

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Aug 20, 2018 at 22:46
  • $\begingroup$ 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"). $\endgroup$
    – vonbrand
    Commented Mar 3, 2020 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.