0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ $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. $\endgroup$
    – zkutch
    Jun 20 '20 at 10:58
  • $\begingroup$ @zkutch Oh oops! Yeah, that's not correct. It would be $O(f(n)^2)$. Take your time :) $\endgroup$ Jun 20 '20 at 11:16
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ No having upper bound doesn't mean, that we cannot state properties on unbounded functions sets. $\endgroup$
    – zkutch
    Jun 21 '20 at 0:51
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.