1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Consider $k=0,1,2,..$ and try to draw this functions. $\endgroup$ – zkutch Feb 26 at 17:27
  • $\begingroup$ 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$. $\endgroup$ – plop Feb 26 at 17:35
  • $\begingroup$ @zkutch I still don't get the meaning of the condition. Can you explain them by words? $\endgroup$ – Tak Feb 26 at 17:39
1
$\begingroup$

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 enter image description here and imagine, that $f$ is one line and $g$ another.

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

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.