Prove or disprove: If $O(\;f(n)\,O(g(n))\;)\in O(\;f(n)\,g(n)\;)$, then $O(\;f(n)\,g(n)\;) \in f(n)\,O(g(n))$

Question

I found this problem on a quiz for a course online and I am utterly stumped as how to proceed:

Prove or disprove: $$\text{If}\;\; O(\;f(n)\,O(g(n))\;)\in O(\;f(n)\,g(n)\;),\;\;\text{then}\;\; O(\;f(n)\,g(n)\;) \in f(n)\,O(g(n))$$

Are there any hints that anyone could give on how to grok playing with asymptotics.

It appears to be a proof of a transitive property of asymptotics, but I am unclear of how to transform the LHS of the first expression with RHS of the second expression.

Answer 1

\begin{align} O(f O(g)) &= \{h \mid \exists C > 0,G\in O(g) : |h|< C |fG| \text{ ev.}\} \\ O(fg) &= \{h\mid \exists C>0 : |h| < C|fg| \text{ ev.}\}\\ fO(g) &= \{h=f H \mid \exists C> 0 : |H|< C|g| \text{ ev.}\} \end{align} If I understand correctly, it makes little sense to impose the assumption "if $O(f O(g)) \in O(fg)$", because $O(f O(g)) $ is equal as sets to $ O(fg)$, so we even have the reverse inclusion.

So the question is just: if $h \in O(fg)$, then is $h \in f O(g)$? If the sets above are defined correctly, the answer is no. This is because there is no longer an $O(\cdot)$ around $f$, allowing the small $n$ behavior of $f$ to matter.

Concrete counterexample: let $\mathbb Z_{\ge 1} = \{ 1,2,3,\dots\}$, and suppose $$g(n)=1,f(n)=n-1,h(n)=2n+10 \text{, }\quad n\in \mathbb Z_{\ge 1}.$$ Then note $f(1)=0$, so every function $\tilde h\in fO(g)$ has $\tilde h(1) = 0$. Thus, $h\notin fO(g)$, eventhough $h\in O(fg) $.

Answer 2

I sat down and thought about this for a long time. I believe this works. I will leave this up here for posterity. Maybe it helps someone else out.

Note that $c*O(f(n)) \in O(f(n))$ where C is a constant and $O(O(f(n))) \in O(f(n))$ and $f(n) \in O(f(n))$.

Given these facts and that $O(f(n)O(g(n)))\in O(f(n)g(n))$ is given we may say that $O(f(n)g(n)) \in f(n)O(g(n))$.

I don't know if it's sufficiently proved but it feels correct.