Question

Find function f and g form the set of positive integers to the set of real numbers such that $f\left(n\right)$ is not$O\left(g\left(n\right)\right)$ and$g\left(n\right)$ is not $O\left(f\left(n\right)\right)$.

Short answer

We have to find the function f and g such that f (n) is not O (g(n)) and g(n) is not O(f(n)) .

Step-by-step solution

Step 1:

In the question it is given that f and g form the set of positive integers to the set of real numbers.

So, f,g:$\backslash \mathrm{user}1Z^{\backslash \mathrm{user}}1+\to \backslash \mathrm{user}1R$

Now let’s look at the function

f(n) = {20

g(n) =$n^2$

Step 2:

Let’s say, n is odd, then

f(n) =$n^3$

g(n) = $n^2$

If n > k then, f(n) > g(n)

Now, by applying the definition of Big-O Notation,$\left|f\right(x\left)\right|\le a\left|g\right(x\left)\right|$

If we compare the two expressions, f(n) > g(n) and $\left|f\right(x\left)\right|\le a\left|g\right(x\left)\right|$

We can say that f(n) is not O(g(n)).

Step 3:

Let’s say, n is even, then

f(n) = n

g(n) = $n^2$

If n > k then, f(n) < g(n)

Now, by applying the definition of Big-O Notation,$\left|f\right(x\left)\right|\le a\left|g\right(x\left)\right|$

If we compare the two expressions, f(n)<g(n) and$\left|f\right(x\left)\right|\le a\left|g\right(x\left)\right|$

We can say that g(n) is not O(f(n)).