If both $t_1(n)$ and $t_2(n)$ are $O(f(n))$, then what is $O(t_1(n) / t_2(n))$?

If both $$t_1(n)$$ and $$t_2(n)$$ are $$O(f(n))$$, then what is $$O(t_1(n) / t_2(n))$$?

Here is my reasoning... I know that the following property holds:

$$t_1(n)\cdot t_2(n) = O(f(n) \cdot f(n)) = O(f(n)^2)$$

But the inverse property does not hold:

$$t_1(n)/t_2(n)=O(f(n)/f(n)) = O(1)$$

Since the division property does apparently not hold, does this mean we cannot know $$O(t_1(n)/t_2(n))$$ unless $$t_1(n)$$ and $$t_2(n)$$ are known?

Bonus points if you can also explain why the division property does not hold.

• $O(f(n) \cdot f(n)) = O(f(n))$ are you sure? Sorry, this is my favorite them, but I'll be able to help you only at evening. Jun 20 '20 at 10:58
• @zkutch Oh oops! Yeah, that's not correct. It would be $O(f(n)^2)$. Take your time :) Jun 20 '20 at 11:16

I'll have a go: The division property does not hold because O(f(n)) only gives an upper bound to t2(n), not a lower bound. Some values of t2(n) could be arbitrarily small, so there is no upper bound on t1(n)/t2(n) without further constraints.

• No having upper bound doesn't mean, that we cannot state properties on unbounded functions sets. Jun 21 '20 at 0:51

Firstly, let me bring definition for O-big. For simplicity take case $$f:\mathbb{N}\longrightarrow\mathbb{R}_{\geq 0}$$ and $$g:\mathbb{N}\longrightarrow\mathbb{R}_{\geq 0}$$ $$O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace$$ So, I consider $$O(g)$$ as set of functions and all equality with it as set type equality. There is well know , that $$O(f) \cdot O(g) = O(fg)$$ and as every source consider it as only left to right direction, as "$$\subset$$", and some have proof for it, I'll consider reverse direction, right to left:

I admit for start, that $$f \ne 0$$ and then retire from this restriction. Suppose $$\varphi \in O(fg)$$. This mean $$\exists C > 0, \exists N \in \mathbb{N}, \forall n > N,\ \varphi \leqslant C \cdot f \cdot g$$ i.e. $$\dfrac{\varphi}{f} \leqslant C \cdot g$$, as I have case $$f > 0$$.

Now consider $$\varphi = \dfrac{\varphi}{f} \cdot f$$. It's enough to show $$\dfrac{\varphi}{f} \in O(g)$$, which we already have above.

And I'll get free from $$f \ne 0$$ by considering representation $$\mathbb{N} = \mathbb{N}_{1} \cup \mathbb{N}_{2},\ \mathbb{N}_{1} \cap \mathbb{N}_{2} = \varnothing$$ and $$0 \notin f(\mathbb{N}_{2})$$.

Finally about division. From proved above, for $$f > 0$$, there will be $$O\left(\frac{g}{f}\right) = O\left(g \cdot \frac{1}{f}\right) = O(g)\cdot O\left(\frac{1}{f}\right)$$ This gives, for $$g>0$$ $$O(g)\cdot O\left(\frac{1}{g}\right) = O(1)$$ About "Bonus points", what can and should be division and other brothers, let's continue in comments if/when you count it deserving.