1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 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$ – David Richerby Aug 20 '18 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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