This is a question I got for an assignment, and I have been stuck on it for the past few days.
Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$
Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$
I was able to prove the first part but I am getting stuck in the second part. If someone could help me out with this I would be very grateful.
First, let us explain what the sentence $$ \Theta(n) + \Theta(n-1) = \Theta(n) $$ means. It means the following:
If $f(n) = \Theta(n)$ and $g(n) = \Theta(n-1)$ then $f(n) + g(n) = \Theta(n)$.
(If you're more pedantic, you should replace $=\Theta(\cdot)$ with $\in \Theta(\cdot)$. The notation isn't symmetric. Similarly, the original sentence could have $\subseteq$ in place of $=$.)
You can prove this directly using the definition of $\Theta(\cdot)$:
$\phi(n) = \Theta(\psi(n))$ if there exist $c,C,N>0$ such that for all $n \geq N$: $c\psi(n) \leq \phi(n) \leq C\psi(n)$.
(We tacitly assume that $\psi(n)$ is eventually positive, and $N$ is implicitly assumed to be chosen so that $\psi(n) > 0$ whenever $n \geq N$.)
Now, let us consider your second sentence: $$ \Theta(n) = \Theta(n) - \Theta(n-1). $$ This sentence means that if $f(n) = \Theta(n)$ then there are $g(n) = \Theta(n)$ and $h(n) = \Theta(n-1)$ such that $f(n) = g(n) - h(n)$. This also holds: you can take $g(n) = 2f(n)$ and $h(n) = f(n)$.
However, the right-hand side $\Theta(n) - \Theta(n-1)$ is not so useful, since we cannot say too much about its rate of growth. For one, it is not necessarily eventually positive; but even if we consider its magnitude, all we can conclude is that it is $O(n)$. Due to these reasons, you are unlikely to see a difference of two asymptotic notations, unless the subtrahend is asymptotically smaller than the minuend (and even then, you ought to be very careful).
Here is the general case: if $X$ is an expression involving asymptotic notations $\Upsilon(F_i)$ (where $\Upsilon \in \{O,\Omega,\Theta,o,\omega\}$ could depend on $i$) and $Y$ is an expressions involving asymptotic notations $\Upsilon(G_j)$, then $X=Y$ has the following meaning:
If $f_i = \Upsilon(F_i)$ for all $i$ then there exist $g_j = \Upsilon(G_j)$ for all $j$ such that $$X[\Upsilon(F_i)/f_i] = Y[\Upsilon(G_j)/g_j].$$
Here $Z[s/t]$ denotes the substitution of $t$ for $s$ in $Z$.
One more bit, just to confuse you even further: sometimes asymptotic notation refers to magnitudes of expression. For example, $-n = \Theta(n)$ under this convention. In that setting subtraction makes a bit more sense — but just a little bit.
