[Math] Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$

asymptotics

I believe that my understanding of this question is incorrect, so any help would be appreciated.

The Question:

Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$

Note that for this problem, you are proving that the set of functions on the left hand side is a subset of the set of functions on the right hand side. The set on the left hand side is the algebraic sum of two sets (not the union): an element of the left hand side has the form $f(n)=f_1(n)+f_2(n)$, where $f_1(n)\in\theta(n^2)$ and $f_2(n)\in O(n^3)$

My Question:

Is it safe to assume that $n^2\in\theta(n^2)$ and $n^3\in O(n^3)$?

Thus, $f(n) = n^3 + n^2 $

$f(n) \in O(n^3)$

$n^3 + n^2 \leq cn^3$

$n+1 \leq cn$

$c \geq 2 $

$∴ f(n) ∈ O(n^3 )$ and $f(n) ⊆ O(n^3 )$

Best Answer

Is it safe to assume that $n^2\in\theta(n^2)$ and $n^3\in O(n^3)$. Thus, $f(n) = n^3 + n^2 $

is as valid as

It is safe to assume that the murderer lives in California. You live in California, therefore you are the murderer.

I hope that if you served on a jury and heard the above argument, you'd find a flaw in it.

Anyway, suppose $f\in \theta(n^2)$ and $g\in O(n^3)$. The proof can proceed in two steps.

  1. Show that $f \in O(n^3)$
  2. From $f\in O(n^3)$ and $g\in O(n^3)$ obtain that $f+g\in O(n^3)$

You don't need to know any formula for $f$ or $g$ to run the above argument.

Related Question