Let \(𝑓(𝑛)\) and \(𝑔(𝑛)\) be asymptotically non-negative functions. Which…

Answer: For asymptotically non-negative functions f(n) and g(n), Θ(f(n)+g(n)) = Θ(max(f(n), g(n))).

Proof outline:

• Let h(n) = max(f(n), g(n)).

• Since h(n) is at least each of f(n) and g(n), we have h(n) ≤ f(n) + g(n).

• Also f(n) + g(n) ≤ h(n) + h(n) = 2·h(n).

• Combining these inequalities gives h(n) ≤ f(n)+g(n) ≤ 2·h(n), so by the definition of Θ we conclude f(n)+g(n) = Θ(h(n)) = Θ(max(f(n), g(n))).

Notes on the incorrect statements:

• Claims relating Θ(f(n)*g(n)) to min(f(n), g(n)) or to max(f(n), g(n)) are false in general. For example, f(n)=n and g(n)=n give f(n)*g(n)=n^2 while min and max are n.

• The claim that Θ(f(n)+g(n)) equals min(f(n), g(n)) is false: for f(n)=n^2 and g(n)=n the sum is Θ(n^2) while the minimum is Θ(n).