证明Big-O Sum规则？

Question

我不确定如何正式证明大O的总和规则,即:

f1(n) + f2(n) is O(max(g1(n)),g2(n))

到目前为止,我认为我的努力如下:

要有两个常量c1和c2这样c2 > c1.按大O定义:

f1(n) <= c1g1(n) and f2(n) <= c2g2(n)

我该怎么办？在这一步引入变量的数值替换来证明这种关系是否合理？不知道g或者f,这是我能想到的唯一方法.

Answer 1

让

gmax = max(g1, g2), and gmin = min(g1, g2). 

gmin是O(gmax).现在,使用定义:

gmin(n) <= c*gmax(n) for n > some k

向每一侧添加gmax(n)给出:

gmin(n) + gmax(n) <= c*gmax(n) + gmax(n) for n > some k
gmin(n) + gmax(n) <= (c+1)*gmax(n)       for n > some k
g1(n) + g2(n) <= c'*gmax(n)              for n > some k

所以我们有g1 + g2是O(max(g1,g2)).

由于f1 + f2是O(g1 + g2),因此big-O的传递性使得f1 + f2为O(max(g1,g2)).QED.