$f,g:\mathbb{N}\to\mathbb{N}$ increasing implies $g\in \Omega(max(f(n),g(n))$ or $f\in \Omega(max(f(n),g(n))$

Question

studying for a test I encountered a problem that should be easy. Unfortunately, I fail to solve it.

let $f,g:\mathbb{N}\to\mathbb{N}$ be increasing functions. assume $f\notin \Omega(max(f(n),g(n))$, does $g\in \Omega(max(f(n),g(n))$ necessarily?

Any help would be appreciated

Answer 1

No. Start with $f(1)=2, g(1)=1$, then (*) take $f(n+1)=f(n)+1$, $g(n+1)=2g(n)$ until $g(n) > f(n)^2$. Then, say that $g(n+1)=g(n)+1$ and $f(n+1)=2f(n)$ till $f(n) > g(n)^2$.

Start the process again from (*).

$f$ and $g$ are increasing, for infinitely many $n$ $f(n) > g(n)^2$, and for infinitely many $n$ $g(n) > f(n)^2$.

Answer 2

No. $f(n) = n \times 2^{n\lfloor \frac{n}{5} \rfloor}$ and $g(n) = 2^{n\lfloor \frac{n+1}{5} \rfloor}$. Both functions are strictly increasing.

For the values of $n$ s.t. $\lfloor \frac{n}{5}\rfloor = \lfloor \frac{n+1}{5} \rfloor$ the equation $f(n) = n \times g(n)$ holds. For the other values of $n$ the equation $\ln g(n) = n +\ln f(n)$ which implies that $g(n) \geq 2^nf(n)$ for those values of $n$.