算法复杂度计算中Max{f,g}=O（f+g）是否正确?如果正确的话错误的话请举例.注意,需要证明的原题是Max{f,g}=O（f+g）,不是O（Max{f,g}）=O（f+g）

Question

算法复杂度计算中 Max{f,g} = O （f + g ）是否正确?
如果正确的话 错误的话请举例.
注意,需要证明的原题是 Max{f,g} = O （f + g ）,不是O（Max{f,g}） = O （f + g ）

Answer 1

这里前提需要假设 f ≥ 0 , g ≥ 0
那么 max{f,g} ≤ f + g
所以存在 N = 1 , C = 1.
满足对任意的 x ≥ N , 有 max{f,g} ≤ 1*(f + g)
即: max{f,g} = O(f + g)
证毕#
这里注意反例, 如果没有min{f,g} ≥ 0的条件:
令 f(x) = -x ; g(x) = x;
有 max{f,g} = |-x| - x ;
f + g = 0
那么不存在 实数 C ,也不存在正整数N ,
满足对任意的 x ≥ N ,有 max{f,g} ≤ C*0 = 0