I have to decide, wether the following theorem is right or wrong. There are functions, that satisfy the following conditions:

$ f(n) \in \mathcal{O}(h(n)) $ and $ g(n) \in \mathcal{O}(h(n))$

Now it should hold: $$ \frac{f(n)}{g(n)} =\mathcal{O}(1) $$

By definition I get: $f(n) \leq c_1 \cdot h(n) \ \forall n\geq N$ and $g(n) \leq c_2 \cdot h(n) \ \forall n\geq N'$

So, $$ \frac{f(n)}{g(n)} = \frac{c_1}{c_2} \cdot 1 \ \forall n\geq max\{N,N'\}$$

I'm not sure. g(n) could be 0. What do you think?

  • 3
    $\begingroup$ I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly? $\endgroup$ – Eric Lippert Apr 26 '19 at 15:13
  • $\begingroup$ @EricLippert It is extremely common in big O notation to mix and match the element symbol and equality symbol. They both mean element of. Yes it's very confusing. $\endgroup$ – Brady Gilg May 1 '19 at 18:35

You can't go from $f \leqslant c_1 h$ and $g \leqslant c_2 h$ to $\frac{f}{g} = \frac{c_1}{c_2}$.

And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.

| cite | improve this answer | |
  • $\begingroup$ Why can't I go to $ \frac{f}{g}$ $\endgroup$ – Leon1998 Apr 26 '19 at 11:01
  • $\begingroup$ Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $\frac{1}{3} \neq \frac{2}{4}$. May be you wanted to write $\frac{f}{g} \leqslant \frac{c_1}{c_2}$? It's still not true: you have $\frac{1}{g} \geqslant \frac{1}{c_2 h}$, but you can multiply inequalities only with same direction. $\endgroup$ – mihaild Apr 26 '19 at 11:06
  • 1
    $\begingroup$ Ok thank you. Now I see my mistake:) $\endgroup$ – Leon1998 Apr 26 '19 at 11:34

Consider $f(n)=h(n)=1$ and $g(n)=1/n$.

| cite | improve this answer | |

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.