# Big O /Right or wrong?

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?

• 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? – Eric Lippert Apr 26 at 15:13
• @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. – Brady Gilg May 1 at 18:35

## 2 Answers

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$$.

• Why can't I go to $\frac{f}{g}$ – Leon1998 Apr 26 at 11:01
• 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. – mihaild Apr 26 at 11:06
• Ok thank you. Now I see my mistake:) – Leon1998 Apr 26 at 11:34

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