I am stuck at the following question:
This question has already been asked on this forum here and here
In the first link the question didn't receive any answers especially the part that I am interested in, and about the second link honestly I am not sure it is possible to do it the way they did.
If $f$ and $g$ are monotonically increasing functions, such that $f(g(n))=O(n)$ and $f(n)=Ω(n)$ then $g(n)=O(n)$.
I think I understand what is going on but I am struggling to prove it.
We know that $f(n)$ grows at least as fast as $n$ so if $g(n)$ will grow faster then $n$ -
$f(g(n))$ will grow faster then $n$ which will lead us to $f(g(n)) \neq O(n)$ and we will get a contradiction. The problem is that I have no Idia how to format the answer correctly.
Please help me if you can.
The facts that $f(n) \in \Omega(n)$ and $f(g(n)) \in O(n)$ tell us that $\frac{f(g(n))}{n} \le C_1$ and $C_2 \le \frac{f(n)}{n} \le C_3$ (for $n$ large enough). Now, if $g(n)$ is unbounded, then the quotient $\frac{f(g(n))}{g(n)}$ behaves like $\frac{f(n)}{n}$ and gets larger than, say, $C_2/2$. Then $$\frac{f(g(n))}{n} = \frac{f(g(n))}{n}\cdot \frac{g(n)}{g(n)} = \frac{f(g(n))}{g(n)}\cdot\frac{g(n)}{n}$$
shows, because the LHS is bounded above by $C_1$, that we must have $\frac{g(n)}{n} \le C$ for some $C$ also, since otherwise the RHS would grow arbitrarily large, given that $\frac{f(g(n))}{g(n)}$ would be bounded below and $\frac{g(n)}{n}$ would diverge to infinity.
Otherwise, if $g(n)$ is bounded, then it tends to a limit $L$, and we obviously have $\frac{g(n)}{n} \to 0$ since the numerator tends to $L$ and the denominator to $\infty$.