سوال ۶۶ کنکور ارشد علوم کامپیوتر ۱۴۰۰

Recall the definition: $f = O(h)$ means there exist constants $c > 0$ and $n_0$ such that $f(n) \le c\cdot h(n)$ for all $n \ge n_0$. Because the codomain is $\mathbb{N}$, every value is non-negative: $f(n) \ge 0$ and $g(n) \ge 0$. This non-negativity is what makes both statements hold.

Statement (a): $f = O(3f)$. We need $f(n) \le c \cdot 3f(n)$. Pick $c = 1$ (or even $c = \tfrac{1}{3}$): $f(n) \le 3\,f(n) \quad\text{for all } n,$ which holds since $f(n) \ge 0$. So (a) is true. (This is just the general fact that constant factors don't matter in $O$-notation: $f = \Theta(cf)$ for any constant $c>0$.)

Statement (b): $f = O(f+g)$. We need $f(n) \le c\,(f(n)+g(n))$. Pick $c = 1$: $f(n) \le f(n) + g(n) \quad\text{for all } n,$ which holds since $g(n) \ge 0$. So (b) is true. Intuitively, adding a non-negative term can only make the right side larger, so $f+g$ is an asymptotic upper bound for $f$.

Both statements are true, so the answer is Both (option 3).

Pitfall: Statement (b) would fail if $g$ could take negative values (e.g. $g = -f$ gives $f+g = 0$, and then $f \ne O(0)$ unless $f \equiv 0$). The codomain $\mathbb{N}$ guarantees $g \ge 0$, which is exactly why the bound goes through.