f(n) +ο(f(n)) =Θ(f(n))的证明

Question

你能帮我证明一下吗？我试着设置o( f(n) )= g(n)，然后试着解方程f(N)+ g(n) =Θ(f(n))，但我不知道这是不是正确的方法，如果是的话，我不知道如何继续我的解。谢谢

Answer 1

假设所有的函数都是非负的(否则你需要调整下面的证明和定义来处理符号)。

设g(n) = o(f(n))。这意味着对于所有的c>0，有一个N使得n>N隐含g(n) < cf(n)。因此，特别是有一个N使得n>N意味着g(n) < f(n) (即:在定义中选择c=1 )。

从函数非负的假设出发，我们还得到f(n) <= f(n) + g(n)。

对于n>N，我们有f(n) <= f(n) + g(n) < 2f(n)，从而f(n) + g(n) = n>N (f(N))。