1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Jan 23 at 21:09
  • $\begingroup$ In asymptotic notation, "$=$" doesn't signify equality. It signifies set inclusion. $\endgroup$ Jan 23 at 22:37
  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Jan 23 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.