Is it right to say that suppose we have two monotonically increasing functions f,g so that f(n)=Ω(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.
I believe this claim is true. Here's a proof.
Suppose that f(n) = Ω(n). That means that there are constants c, n0 such that
f(n) ≥ cn for any n ≥ n0. (1)
Similarly, since f(g(n)) = O(n), we know that there are constants d, n1 such that
f(g(n)) ≤ dn for any n ≥ n1. (2)
Now, there are two options. The first is that g(n) = O(1), in which case we're done because g(n) is then O(n). The second case is that g(n) ≠ O(1), in which case g grows without bound. That means that there is an n2 such that g(n2) ≥ n0 (g grows without bound, so it eventually overtakes n0) and n2 ≥ n1 (just pick a big n2).
Now, pick any n ≥ n2. Since n ≥ n2, we have that g(n) ≥ g(n2) ≥ n0 because g is monotone increasing, and therefore by (1) we see that
f(g(n)) ≥ cg(n).
Since n ≥ n2 ≥ n1, we can combine this inequality with equation (2) to see that
dn ≥ f(g(n)) ≥ cg(n).
so, in particular, we have that
g(n) ≤ (d / c)n
for all n ≥ n2, so g(n) = O(n).