Asymptotic bound with square-roots Let $f(n)$ and $g(n)$ be two increasing functions of $n$ such that:
$$ f \leq g + O(\sqrt{g}) + O(\sqrt{f}) $$
Is it true that:
$$ f \leq g + O(\sqrt{g}) $$
? If not, then what would be a good asymptotic upper bound on $f$?
NOTE: the asymptotic behavior is when $n\to\infty$.
 A: This does not hold; for instance, take the following, where the asymptotics are taken around $+\infty$:
$$
f(x) = \frac{1}{x}, \qquad g(x)=\frac{1}{x^3}
$$
Then $$f(x) = \frac{1}{x} \leq \frac{1}{x^3} + O(x^{-3/2}) +  O(x^{-1/2}) = O(x^{-1/2})  = O(\sqrt{f(x)})$$
but we do not have $f(x) \leq x^{-3} + O(x^{-3/2}) = O(x^{-3/2})$. You can adapt this example to other situations: you cannot get a better bound only in terms of $g$, since if the "relevant" upper bound from the first line if $f=O(\sqrt{f})$ then $g$ and $f$ can be arbitrarily unrelated.

Following the clarification from the OP:
Now, assuming further that $f\nearrow \infty$ and $g$ is non-decreasing: $\sqrt{f} = o(f)$, so that we must have $f \leq g + O(\sqrt{g})$. Indeed, dividing by $\sqrt{f}$, we get
$$
\sqrt{f} \leq \frac{g}{\sqrt{f}} + O\left(\sqrt{\frac{g}{f}}\right) + O(1)
$$
and since the LHS goes to infinity, so does the RHS. this implies in turn that $\sqrt{g}=o(g)$: otherwise, we do not have $g\to\infty$, so by monotonicity $g$ converges to a finite limit, and thus so does $\sqrt{g}$: the RHS does not go to infinity.
It follows that $\sqrt{g}=o(g)$, and therefore $g\nearrow\infty$; and we also get that $g = \Omega(f)$. Indeed, otherwise we would have $g=o(f)$ (not quite, but for a subsequence at least -- ignoring this detail), so that we would get, from the beginning:
$$
f \leq o(f) + O(\sqrt{f}) = o(f)
$$
which is impossible. Finally, this means that $\sqrt{g} = \Omega(\sqrt{f})$, and therefore
$$
f \leq g + O(\sqrt{g}).
$$
