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

120 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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.

1
On

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.