0
$\begingroup$

Prove that $\forall f : \mathbb{N} \to \mathbb{R^+},(\exists g : \mathbb{N} \to \mathbb{R}^{\geq 0}, g \not \in \mathcal{O}(f) \land g \not \in \Omega (f)$.

Recall that the definition of Big-Oh is $$\exists c \in \mathbb{R}^+, \exists n_0 \in \mathbb{R}^+, \forall n \in\mathbb{N}, n \geqslant n_0 \Rightarrow g(n) \leq cf(n)$$ and Big-Omega is $$\exists c \in \mathbb{R}^+, \exists n_0 \in \mathbb{R}^+, \forall n \in\mathbb{N}, n \geqslant n_0 \Rightarrow g(n) \geq cf(n)$$

I'm having a real tough time with this... I'm starting to think it's not true. My gut instinct is definitely telling me that the codomain of $f$ being positive as opposed to non-negative is important.

I started drawing some pictures but it's leading me nowhere. Could anyone help?

$\endgroup$

1 Answer 1

0
$\begingroup$

Take $g(n)=nf(n)$ if $n$ is even and $f(n)=\frac 1 n f(n)$ if $n$ is odd.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .