0
$\begingroup$

Consider g a function of n: $g(n)$.

Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + h(n)$ with respect to $g(n)$?

Given that $f(n)$ is $Θ(g(n))$, I have that $f(n)$ grows the same way as $g(n)$.
Given that $h(n)$ is not $O(g(n))$, I have that $h(n)$ grows more rapidly compared to $g(n)$.

In my mind, at least, it seems like these two above observations are sufficient to conclude that $f(n) + h(n)$ grows (just like $h(n)$) more rapidly than $g(n)$ and, thus, $ f(n) + h(n) \in O(g(n))$, but I'm afraid it's a counterintuitive case or I'm missing something.

$\endgroup$
0
$\begingroup$

Suppose $f\in \Theta(g)$ and $h\notin \mathcal{O}(g)$. That means: $$\exists A>0, B>0, \forall n\geqslant 0, Ag(n) \leqslant f(n) \leqslant Bg(n)$$ and $$\forall C>0, \exists n\geqslant 0, h(n) > Cg(n)$$

Therefore, for all $C>0$, there exists $n\geqslant 0$ such that $h(n) > (C-A)g(n)$. We conclude that $f(n) + h(n) > Ag(n) + (C-A)g(n) = Cg(n)$.

We just proved that $f +h\notin\mathcal{O}(g)$.

Note that I supposed here that all functions are positive.

$\endgroup$

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.