Please write your answers in a legible way and submit a single pdf file. 1. Consider functions \( f_{1}, f_{2}: \mathbb{N} \rightarrow \mathbb{R} \) which are asymptotically positive. Using the definitions show that if \( f_{1}=O\left(f_{2}\right) \) then \( f_{1}+f_{2}=\Theta\left(f_{2}\right) \).
Real Tutor Solution
Answer
Solution
Reviewed and approved by the UpStudy tutoring team
Explain 
Simplify this solution Extra Insights
To show that \( f_{1} + f_{2} = \Theta(f_{2}) \) under the condition that \( f_{1} = O(f_{2}) \), we first recall the definitions involving Big O and Big Theta notation. By definition, \( f_{1} = O(f_{2}) \) means that there exist positive constants \( C \) and \( n_{0} \) such that for all \( n \geq n_{0} \): \[ f_{1}(n) \leq C \cdot f_{2}(n). \] This indicates that \( f_{1} \) grows at a rate that is bounded above by some constant multiple of \( f_{2} \) for sufficiently large \( n \). Now, when we consider \( f_{1} + f_{2} \), we can express it as follows: \[ f_{1}(n) + f_{2}(n) \leq C \cdot f_{2}(n) + f_{2}(n) = (C + 1) \cdot f_{2}(n). \] This shows that \( f_{1} + f_{2} \) is \( O(f_{2}) \). To satisfy the other requirement for \( \Theta(f_{2}) \), we need to establish the opposite inequality. Notice that since \( f_{2} \) is asymptotically positive, for sufficiently large \( n \), \( f_{2}(n) > 0 \). Thus: \[ f_{1}(n) + f_{2}(n) \geq f_{2}(n) \quad \text{(because \( f_{1} \) is always non-negative)}. \] This means \( f_{1} + f_{2} \) is lower bounded by \( f_{2}(n) \). Combining both results, we have: \[ f_{1} + f_{2} = O(f_{2}) \quad \text{and} \quad f_{1} + f_{2} \geq f_{2}, \] which implies: \[ f_{1} + f_{2} = \Theta(f_{2}). \] Thus, we have shown that if \( f_{1} = O(f_{2}) \), then it indeed follows that \( f_{1} + f_{2} = \Theta(f_{2}) \).
