Two functions whose order can't be equated - big O notation

633 Views Asked by At

Our teacher talked today in the class about big O notation, and about order relations.

she mentioned that the set of order of magnitude, is not linear

Meaning, there are function $f,g$ such that $f$ is not $O(g)$ and $g$ is not $O(f)$, but she gave no such example and im having trouble coming up with one.

Just out of sheer curiosity, could anyone come up with such 2 functions?

2

There are 2 best solutions below

1
On BEST ANSWER

$f(x)=x^2\sin x$ and $g(x)=x.$

0
On

Let

$$f(x)= \begin{cases} x^2 & 2n\le x<2n+1 \\ 1 & 2n+1\le x < 2n+2\end{cases}$$ and $g(x) = x$.