Is it right to say that suppose we have two monotonically increasing functions $f,g$ so that $f(n)=\Omega(n)$ and $f(g(n))=O(n)$. Then I want to conclude that $g(n)=O(n)$.
I think that this is a false claim, and I've been trying to provide counter example to show that this is false claim, but after many attempts I'm starting to think otherwise.
Can you please provide some kind of explanation or example if this is a false claim or a way to prove if it's a correct one.
If by $f(n)=\Omega(n)$ you mean $f(n) > cn$ for all $n$, then the answer is yes, since then $cg(n) < f(g(n)) < Cn$ implies $g(n) < \frac Cc n$.
But probably by $f(n)=\Omega(n)$ you mean $f(n) > cn$ for infinitely many $n$, and there the answer is no.
For a counterexample, let both $f(n)$ and $g(n)$ equal $k!$ on the interval $((k-1)!,k!]$ for every $k\ge2$. Then $f(n)=\Omega(n)$ as witnessed by its values on the sequence $(k!)$; and $f(g(n)) = f(n) \le n$ for all $n$; but $g(n)/n$ is unbounded above, as witnessed by the sequence $((k-1)!+\varepsilon)$.
(It's easy to tweak this example to make the functions strictly increasing and smooth, if needed.)
