Question

Prove that Θ(n−1)+Θ(n)=Θ(n). Does it follow that Θ(n)=Θ(n)−Θ(n−1)? Justify your answer.

Answer 1

To prove that Θ(n−1)+Θ(n)=Θ(n), we show that it is bounded from above and from below by Θ(n). However, Θ(n)=Θ(n)−Θ(n−1) does not necessarily hold.

Step-by-step explanation:

In order to prove that Θ(n−1)+Θ(n)=Θ(n), we need to show that Θ(n−1)+Θ(n) is bounded both from above and from below by Θ(n).

Proof:

1. For the upper bound, we have Θ(n−1)+Θ(n) ≤ Θ(n)+Θ(n) = 2Θ(n), which is clearly a Θ(n) function.
2. For the lower bound, we can express Θ(n−1) as Θ(n-1+1) = Θ(n), and therefore Θ(n−1)+Θ(n) ≥ Θ(n)+Θ(n) = 2Θ(n), which is also a Θ(n) function.

Therefore, Θ(n−1)+Θ(n)=Θ(n).

However, it does not necessarily follow that Θ(n)=Θ(n)−Θ(n−1). The reason is that Θ(n−1) could be a larger class of functions than Θ(n), in which case subtracting Θ(n−1) from Θ(n) would not guarantee that the result is still in the class Θ(n).