加法下渐近有界函数的闭包证明

Question

我想证明这个说法：

如果 f(n) 是 Theta(h(n)) 并且 g(n) = O((h(n)) 那么 f(n) + g(n) 是 O(h(n)) .

假设所有函数都是非负且单调非递减的。

我尝试证明如果 f(n) 和 g(n) 是 O(h(n)) 那么存在：

正常数 n0, c0 使得 f(n) <= c0*h(n) 对于所有 n >= n0

正常数 n1, c1 使得 f(n) <= c1*h(n) 对于所有 n >= n1

因此可以推导出 g(n) + f(n) <= (c1 + c0) * h(n) 对于所有 n >= max(n1, n0) 意味着 g(n) + f(n) 是 O(h(n))

这是正确的吗？有没有更严谨的证明……比如反证法？

Answer 1

你的证明是正确和严谨的。这是直接和建设性的证明，因为您不仅证明了合适的 c 和 n0 存在，而且还说明了如何根据假设计算它们。这里没有想到其他更简单的证明方法。