algorithm - 证明 f(n) + g(n) 是 O(max(f(n),g(n)))

Question

您好，我在证明以下内容时遇到了一些困难。

f(n) + g(n) is O(max(f(n),g(n)))

这是合乎逻辑的，通过查看这个我可以告诉你它是正确的，但我无法提出一个证明。

这是我到目前为止所拥有的：

c * (max(f(n),g(n))) > f(n) + g(n) for n > N

但是我不确定如何选择 ac 和 N 来适应定义，因为我不知道 f(n) 和 g(n) 是什么。

任何帮助表示赞赏。

Answer 1

f(n) + g(n) <= 2* max{f(n),g(n)} 
(for each n>0, assume f(n),g(n) are none-negative functions)

因此，对于N=1，对于所有n>N: ，我们可以根据大 O的f(n) + g(n) <= 2*max{f(n),g(n)}定义说f(n) + g(n)O(max{f(n),g(n)})

所以基本上，我们使用N=1, c=2定义的形式证明。