证明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:f(n) + g(n) <= 2*max{f(n),g(n)},我们可以通过大惟愿的定义,说f(n) + g(n)是O(max{f(n),g(n)})

基本上,我们N=1, c=2根据定义用于形式证明.