The question asks to find three functions, $f(n). g(n), h(n)$ that satisfy the following conditions

Question

The question asks to find three functions, $f(n). g(n), h(n)$ that satisfy the following conditions:

the conditions are:

$f \not \in O(h)$

$g \in \Omega (h)$

$(f-g) \in O (h)$

$(f-g) \not \in \Omega (h)$

from these four condition I've gathered that $f>h$, $g>h$ and $f-g<h$

So my answer is $h = n$, $f=n^2+3$, $g=n^2$.

Is my answer correct?:

Answer 1

Your answer fulfills the required criteria, as $$ \begin{align} n^2+3&\notin O(n)\\ n^2&\in \Omega(n)\\ n^2+3-n^2 = 3&\in O(n)\\ 3&\notin \Omega(n) \end{align} $$ So yes, it is correct.

(I am also happy to see "$\in O(n)$" rather than "$=O(n)$".)

However, regarding your analysis, I would say that $g\geq h$, rather than $g>h$.

Answer 2

Let's check:

• $f\not\in O(h)$ since $f$ is quadratic while $h$ is linear (i.e. $f$ has a higher polynomial order).
• $g\in\Omega(h)$ for the same reasons as the preceding condition.
• $f-g=3\in O(h)$. This is certainly true, since we can select the multiplicative factor to be $1$, and then $3<h(n)$ for sufficiently large $n$.
• $f-g\not\in\Omega(h)$ since $3$ grows strictly slower than $h(n)=n$.

So your functions are one possible correct answer.