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

Question

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

The Question:

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

The only thing I was given is...
f(n)=f_1 (n) + f_2 (n) & f_1 (n) ∈ θ(n^2) & f_2 (n) ∈ O(n^3 ) — Jan Christian, Sep 15 '13 at 02:53
what i mean is what does elements of $\theta(n^2)$ looks like?? — , Sep 15 '13 at 02:54
Usually $f\in\theta(g)$ is equivalent to (if not defined as) $f\in O(g)$ and $g\in O(f)$, if that helps. — Richard Rast, Sep 15 '13 at 03:03
@PraphullaKoushik, it stands for Big Theta Notation. In a sense, it is the average-time an algorithm will take to run. Or the average amount of iterations for which it will run. — David, Sep 15 '13 at 07:28
@PraphullaKoushik, no problem. It is in the family of Big Oh and Big Omega. Check 'em out. It's interesting. I'm tempted to say he should have posted this in Stackoverflow, not Mathematics. — David, Sep 15 '13 at 08:40

score 1 · Answer 1 · answered Oct 05 '13 at 15:03

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.

Show that $f \in O(n^3)$
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.

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

1 Answers1