Check if $f(n)+g(n)=O(\min \{ f(n), g(n) \})$

4.8k Views Asked by At

Let $f(n)$ and $g(n)$ be asymptotically positive functions.

I want to check if $f(n)+g(n)=O(\min \{ f(n), g(n) \})$.

That's what I have tried:

Let $f(n)+g(n)=O(\min \{ f(n), g(n) \})$. Then, $\exists c>0 , \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0:$

$$f(n)+g(n) \leq c (\min \{ f(n), g(n) \})$$

Let $\min \{ f(n), g(n) \}=f(n)$

Then,

$$f(n)+g(n) \leq c f(n) \Rightarrow g(n) \leq (c-1)f(n), \text{ that is a contadiction } \forall c$$

Can I do it like that or do I have do find a counterexample?

1

There are 1 best solutions below

2
On BEST ANSWER

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