Let \(f(n)\) and \(g(n)\) be asymptotically nonnegative functions. Using the basic definition of \(\Theta\)-notation, prove that \(\max(f(n),g(n)) = \Theta(f(n) + g(n))\).

\(f(n)\) and \(g(n)\) being asympototically nonnegative functions means that \(0 \leq f(n)\) and \(0 \leq g(n)\) which implies:

\[0 \leq f(n) + g(n)\]

Taking the max of two integers results in one of those two values which gives us \(f(n) \leq \max(f(n), g(n))\) and \(g(n) \leq \max(f(n), g(n))\) and happens to imply \(\frac{f(n) + g(n)}{2} \leq \max(f(n), g(n))\). We can combine this with our above inequality by first multiplying both sides by \(\frac{1}{2}\):

\[0 \leq \frac{f(n) + g(n)}{2} \leq \max(f(n), g(n))\]

Lastly, \(\max(f(n), g(n))\) is always less than or equal to the sum of its two terms (since we know they are not negative). This tells us \(\max(f(n), g(n)) \leq f(n) + g(n)\). This gives us the following inequality:

\[0 \leq \frac{f(n) + g(n)}{2} \leq \max(f(n), g(n)) \leq f(n) + g(n)\]

Which is the definition of \(\Theta\)-notation with \(c_1 = \frac{1}{2}\) and \(c_2 = 1\).