To prove that $f(n) + g(n) = O(n^2)$, we need to show that there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$:

$f(n) + g(n) \leq c \cdot n^2$

Given:

$f(n) = 3n^2 - n + 4$ $g(n) = n \log n + 5$

Step 1: Analyze $f(n)$

The function $f(n) = 3n^2 - n + 4$ is a quadratic function. We know that for sufficiently large $n$, the $3n^2$ term will dominate the linear term $-n$ and the constant term $4$. Therefore:

$f(n) \approx 3n^2$

Clearly, $f(n) \leq 4n^2$ for large $n$. Thus:

$f(n) = O(n^2)$

Step 2: Analyze $g(n)$

The function $g(n) = n \log n + 5$ is composed of a term $n \log n$ which grows faster than any linear function of $n$ but slower than any quadratic function of $n$. We can express $g(n)$ as:

$g(n) \leq n \log n + 5 \leq n^2 \text{ for large } n$

This is because $n \log n$ grows slower than $n^2$. Therefore:

$g(n) = O(n^2)$

Step 3: Combine $f(n)$ and $g(n)$

Now, consider the sum $f(n) + g(n)$:

$f(n) + g(n) = (3n^2 - n + 4) + (n \log n + 5) = 3n^2 + n \log n - n + 9$

For large $n$, the dominant term here is $3n^2$. Therefore:

$f(n) + g(n) \leq 3n^2 + n \log n + 9 \leq 4n^2 \text{ for large } n$

Thus, $f(n) + g(n) = O(n^2)$.

Conclusion

We have shown that both $f(n)$ and $g(n)$ are $O(n^2)$, and therefore their sum $f(n) + g(n)$ is also $O(n^2)$.

Would you like to go over any part of this proof in more detail or do you have any questions?

Here are 5 related questions you might find interesting:

1. How would the analysis change if $f(n)$ was a cubic function?
2. Can $f(n) + g(n)$ be $O(n \log n)$?
3. What if $g(n) = n^2 \log n$? How would that affect the proof?
4. How can we prove that a function is $\Omega(n^2)$?
5. What is the difference between $O(n^2)$ and $\Theta(n^2)$?

Tip: When proving a function is $O(g(n))$, focus on identifying the dominant term for large $n$.