Prove that one can always squeeze another function between $f$ and $g$ if $f = O(g)$ and $\neg (g = O(f))$

Question

Let's use $f<g$ to denote that $f = O(g)$ and $\neg(g = O(f))$.

I need to prove that, given $f < g$, we can always find another function, say h, which satisfies: $$f < h < g$$

My first guess is that $$h = (f+g)/2$$ would work. Let's take an example: $f(n) = n^2$, $g(n) = 3^n$. Then, $$h(n) = \frac{3^n + n^2}{2} = \frac{3^n}{2} + \frac{n^2}{2}$$ Which seems to work.

Is this attempt a valid way to solve the problem?

Answer 1

No, it is not true (with your definition of $<$). In your example, $g = O(h)$.

However, you might try $h = \sqrt{|fg|}$