[Math] Proving Big O and Theta notations of functions are in the subset of Big O

asymptotics

HOMEWORK QUESTION
Prove that Θ(n) + O(n^2) ⊆ O(n^2). Note that for this problem, you are proving that the set of functions on the left hand side (LHS) is a subset of the set of functions on the right hand side (RHS). The set on the LHS is the algebraic sum of two sets (not the union): an element of the LHS has the form f(n) = f1(n) + f2(n), where f1(n) ∈ Θ(n) and f2(n) ∈ O(n2).

I conceptually understand O/Theta/Omega notations fairly well I'd say, I'm just having a problem knowing how to start this proof, or how to go about showing it. I think having the '⊆' instead of '∈' is confusing me as well. Any help is appreciated.

Best Answer

Xue right? Looks like we're classmates.

Observe that since $f_1 \in \Theta (n)$, then

$f_1 (n) \le c_1 \bullet n$ $\forall n \ge N$

and also that

$c_1 \bullet n \le c_1 \bullet n^2$

so

$f_1(n) \le c_1 \bullet n \le c_1 \bullet n^2$

Thus

$f_1 \in O(n^2)$

similarly, since $f_2 \in O(n^2)$,

$f_2(n) \le c_2 \bullet n^2$ $\forall n \ge N$

Then

$f_1(n) + f_2(n) \le (c_1+c_2)n^2$ $\forall n \ge N$

And

$\Theta(n) + O(n^2) \subseteq O(n^2)$

I'm not 100% on this, but it makes sense to me so unless I can think of something better it's what I'll submit.