algorithm - 是否有可能证明 f(n) + g(n) = theta(n^2) for f(n) = theta(n^2) & g(n) = O(n^2)

Question

有没有办法证明

f(n) + g(n) = theta(n^2)

还是不可能？假设 f(n) = theta(n^2) & g(n) = O(n^2)

我尝试了以下方法:f(n) = O(n^2) & g(n) = O(n^2)。我证明了

0 <= f(n) <= c1*n^2 
0 <= f(n) <= c2*n^2
for c1 > 1 & c2 > 1

Answer 1

是的，你可以证明这一点。

• f(n)在Theta(n^2) , 所以存在常量 c1,c2,N ， 这样的对所有n>N1 f(n) 是有界的:c1*n^2 <= f(n) <= c2*n^2 (经过定义)
• g(n)在O(n^2) , 所以存在常量 c3,N2这样对于所有n>N2 , g(n) 是有界的:g(n) <= c3*n^2 (根据定义)

现在，看看f(n)+g(n)对于 n>max{N1,N2} :

f(n) + g(n) <= c2*n^2 + c3*n^2 = (c2+c3)*n^2

此外，假设 f(n)是非负的，c1*n^2 <= f(n) <= f(n) + g(n) , 再次为 n>max{N1,N2}>=N1 .

我们得到了 N=max{N1,N2} , 存在常量 c=c1, c'=(c2+c3) , 这样对于所有 n>N

c*n^2 <= f(n) + g(n) <= c'*n^2

根据大 Theta 的定义，这意味着 f(n)+g(n)在Theta(n^2)