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

但我不确定如何选择 c 和 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 : f(n) + g(n) <= 2*max{f(n),g(n)} ，我们可以根据大 O 的定义说 f(n) + g(n)在O(max{f(n),g(n)})

所以基本上，我们使用 N=1, c=2根据定义进行正式证明。