Assume $f(n)=O(g(n))$ with $g(n)\geq 2$ for all $n$

Question

Assume $f(n)=O(g(n))$ with $g(n)\geq2$ for all $n$

implies $f(n)+g(n)=O(g(n))$

the answer which teacher offer is false ，but I think it is true

this is my think

$f(n)=O(g(n))$ so $f(n)\leq c\cdot g(n)$ ,$f(n)+g(n)\leq (c+1)\cdot g(n)$

So $f(n)+g(n)=O(g(n))$

Am I wrong?

You're not wrong, you can be more formal by stating all the quantifiers but besides that you're fine. — Yanko, Jul 11 '19 at 14:29
I'm not sure what the purpose of $g(n)\geq 2$ is in the question. — Thomas Andrews, Jul 11 '19 at 14:31

score 1 · Answer 1 · answered Jul 11 '19 at 14:46

You are correct, and just as a general rule of thumb when there is a linear combination of terms, for example $f(x)=ag(x)+bh(x)+...$ the only term that matters for the asymptotic is the leading(Largest) term. For example $3x^2+99x$ is $O(x^2)$

This can be used to show that you are right since $f(x)\sim O(g(x))$ by assumption and $g(x)\sim O(g(x))$ trivially then $f(x)+g(x)\sim O(g(x))$

Assume $f(n)=O(g(n))$ with $g(n)\geq 2$ for all $n$

1 Answers1