2

True or false.

If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$.

I believe this is false.

Take $f(n) = 4n^2, g(n) = 2n^2$. Then $f(n)-g(n) = 2n^2$ and $2n^2$ is not $\Theta(n^4)$ but I cannot say for sure why.

Can anybody tell me if I am on the right track?

User
  • 907
  • 1
    It is false, you are right – alkabary Jun 06 '15 at 17:28
  • 2
    False, and even: always false, that is, there exists no case where $f(n)\in\Theta(n^2)$, $g(n)\in\Theta(n^2)$, and $f(n)-g(n)\in\Theta(n^4)$, – Did Jun 06 '15 at 17:29
  • Gotcha. In this particular case, $f(n)$ and $g(n)$ will always exist in $\Theta(n^2)$, correct? – User Jun 06 '15 at 17:33
  • A simpler counter-example: $f=g$. Then $(f-g)(n) = 0$, which is $O(n^2)$ but clearly not $\Omega(n^2)$. (In general, you can prove that under your hypothesis $(f-g)(n) = O(n^2)$ (and a fortiori $O(n^4)$ if you want), but not the $\Omega()$ part of the $\Theta()$.) – Clement C. Jun 06 '15 at 17:37

1 Answers1

2

Proving that $\large{f=\Theta(n^2)}$ is the same as showing that $\large{f = O(n^2)}$ and $\large{n^2 = O(f)}$ and so clearly $\large{(f-g)(n) \neq \Theta(n^4)}$ because even though $\large{n^2 = O(n^4)}$ but $\large{n^4 \neq O(n^2)}$ meaning that you cannot find $\large{n_0}$ and $\large{c}$ such that that $\large{n^4 \leq cn^2}$ for all $\large{n \geq n_0}$

alkabary
  • 6,214