Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))?

I don't understand what these function are like and why they satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n)).

Where is x?

$$\begin{eqnarray} f(x)= \begin{cases} k^{2k}, &x\in(2𝑘,2𝑘+1)& \\ k^{2k+1}, &x\in(2𝑘+1,2𝑘+2)& \end{cases} \end{eqnarray}$$

$$\begin{eqnarray} g(x)= \begin{cases} k^{2k-2}, &x\in(2𝑘,2𝑘+1)& \\ k^{2k+2}, &x\in(2𝑘+1,2𝑘+2)& \end{cases} \end{eqnarray}$$

Also, could you teach me how to write these functions in Grapher on MacOS? Cuz I want to know what they are like.

• Consider $k=0,1,2,..$ and try to draw this functions. – zkutch Feb 26 at 17:27
• The function $h(x)=f(x)/g(x)$ is equal to $k^2$ for $x\in(2k,2k+1)$ and equal to $k^{-1}$ for $x\in(2k+1,2k+2)$. The condition $f\in O(g)$ implies that $h=f/g$ is bounded, and $g\in O(f)$ that $1/h$ is bounded. However, $k^2\to\infty$ as $k\to\infty$. – plop Feb 26 at 17:35
• @zkutch I still don't get the meaning of the condition. Can you explain them by words? – Tak Feb 26 at 17:39

Let's firstly imagine function $$f$$: for $$k=2$$ we have two intervals $$(4,5)$$ and $$(5,6)$$ and for $$k=3$$ we have two intervals $$(6,7)$$ and $$(7,8)$$. Accordingly for $$f$$ we have:

$$\quad\quad\quad x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\ f(x)\quad 2^4\quad\quad 2^5\quad\quad\quad 3^6 \quad\quad3^7$$ for function $$g$$ we have: $$\quad\quad\quad x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\ g(x)\quad 2^2\quad\quad 2^6\quad\quad\quad 3^4 \quad\quad3^8$$ So, as you see both $$f$$ and $$g$$ are increasing, but alternately one is more then other with more then constant factor, so they cannot be big-$$O$$ of each other.

To get an idea of an example you can take a look at DNA molecule chain and imagine, that $$f$$ is one line and $$g$$ another.

• Thank you! I finally get it. But still don’t know how I write on the graph drawing software... – Tak Feb 27 at 1:27
• I am using tikz in tex/latex, but it needs some study. – zkutch Feb 27 at 1:54
• I just tried to use tikz and studied a bit. How did you write the code of these functions in tikz? – Tak Feb 27 at 6:02