# Subtraction on Big Theta notation

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.

• What first part you proved? Can you show what you tried. Jan 23 at 17:02
• Use hint, that $\Theta(n)=\Theta(n-1)$. Jan 23 at 18:16

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.

• I can write in separate answer, if you prefer, but second doesn't hold as equality between sets: let's take $n\in \Theta(n)$ and $n\in \Theta(n-1)$. Then we have $f(n)=n-n=0\in \Theta(n)- \Theta(n-1)$. But $0\notin \Theta(n)$, so second cannot be equality between sets, while first is. Jan 23 at 21:09
• In asymptotic notation, "$=$" doesn't signify equality. It signifies set inclusion. Jan 23 at 22:37
• Yes, I know. For example, we can remember D.E. Knuth's "one way equality", but, so many times everybody complain about abuse of notation, that, hope, it comes time to use proper terms: equality in place of equality, inclusion in place of inclusion etc. If we don't start, who will? On other, hand, I think, OP is asking about possible difference between cases and understanding equality as between sets, gives this. Jan 23 at 23:58