If $a(n) + p(n) \in \Theta(b(n) + p(n))$, then $a(n) \in \Theta(b(n))$. True or False?

49 Views Asked by At

If $a(n) + p(n) \in \Theta(b(n) + p(n))$, then $a(n) \in \Theta(b(n))$. Is this statement True or False? I believe it to be False. I have tried proving it to be wrong by assuming its negation and proving that to be true but I think I am missing something in the inequalities. Could someone please point me in the right direction?

The definition of $f(n) \in \Theta(g(n))$ is $\exists c_1, c_2, n_0 \in \mathbb{R^{\leq 0}}, \forall n \in \mathbb{N}, n > n_0 \Rightarrow c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$.

2

There are 2 best solutions below

2
On

You can disprove it by finding a counterexample: Try out what happens for $a(n) = n, p(n) = n^2, b(n) = n^2$

0
On

Hint: What happens if $$\lim_n \frac{a(n)}{p(n)}=\lim_n \frac{b(n)}{p(n)}=0$$?