0

This is a homework question. I have proved before that the sum of the terms on the left-hand-side are a subset of $O(n^3)$, but I have not proved that the two terms are not equal (or whether that was a strict subset, as the $\ne$ implies).

I'm not sure how to proceed or how to use my earlier proof or whether not to do so.

Edit: I have an idea of how to proceed, but I'm not sure how to be explicitly correct about it. I can pick a function of higher order than 3 (say, $n^4$) which would be in $\Theta(n^2)$, and say that that is $O(n^4)$. Therefore, $O(n^4) + O(n^3) \ne O(n^3)$.

Edit 2: None of the above edit is correct.

user473973
  • 207

2 Answers2

2

The two sets are, in fact, equal. You have already shown that $\Theta (n^2) + O(n^3) \subseteq O(n^3)$.

To see why $O(n^3) \subseteq \Theta (n^2) + O(n^3)$, choose any $f \in O(n^3)$. Then we know that there exist some constants $C,n_0$ such that for all $n \geq n_0$, we have: $$ f(n) \leq Cn^3 = (n^2) + (Cn^3 - n^2) $$

It should be easy to see that $n^2 \in \Theta(n^2)$ and $Cn^3 - n^2 \in O(n^3)$. Hence, we have $f \in \Theta (n^2) + O(n^3)$, as desired.

Adriano
  • 41,576
  • But there are functions $f\in O(n^3)$ that cannot be written as the sum of positive functions $g$, $h$ with $g\in\Theta(n^2)$ and $h\in O(n^3)$. – Steven Stadnicki Sep 10 '13 at 23:56
  • I'm not really sure how to approach this question then. It seems that we can reach a contradiction one way yet have it be true another way. – user473973 Sep 11 '13 at 00:04
  • @user473973 One point is that it depends on your definition of $f(n)\in O(g(n))$; I'm making the assumption that the members of $O(g(n))$ are positive functions. The breakdown $f(n) = n^2+g(n)$ in this 'solution' may lead to a $g(n)$ that isn't positive and so isn't in $O(n^3)$ even though its absolute value is bounded by a constant multiple of $n^3$. – Steven Stadnicki Sep 11 '13 at 00:07
  • Oh okay, that's how we learned it (asymptotically positive functions, but still). – user473973 Sep 11 '13 at 00:09
  • @user473973 if your definition requires the functions to be asymptotically positive then this result is incorrect - the function $f(n) = n$ cannot be expressed as the sum of a function $g(n)\in\Theta(n^2)$ and an asymptotically positive $h(n)\in O(n^3)$. – Steven Stadnicki Sep 11 '13 at 00:48
  • 1
    I'm not sure the notation $O$ and $\Theta$ are meant to be summed. Otherwise it seems to me that a function in $\theta(n^2)+O(n^3)$ is required to be bigger than $Cn^2$. Your proof assumes that only one inequality is required, but the $\Theta$ requires two inequalities. – Denis Sep 11 '13 at 00:49
1

The function $f(n)=n^4$ doesn't satisfy $f(n)\in\Theta(n^2)$; I suspect you may be getting $\Theta()$ confused with $\Omega()$.

To see why the inequality doesn't hold (assuming your definition of $O(f(n))$ requires the functions which are members to be positive, which is fairly common), look at the RHS $\Theta(n^2)+O(n^3)$; it's not necessarily true that every function in this set grows as fast as $Cn^3$, but it is the case that every function in this set must grow as fast as $Cn^2$ for some $n$ (since it's the sum of a function $\in\Theta(n^2)$ which grows that fast and a function $\in O(n^3)$ which is positive). Can you think of any functions in $O(n^3)$ which don't grow as fast as $\Theta(n^2)$?

Steven Stadnicki
  • 51,746