证明如果 h(n) > f1(n) - f2(n) > 0 和 f1(n) = Ω(g(n) and f2(n) = O(g(n)) 那么 h(n) = Ω (g(n)
Prove if h(n) > f1(n) - f2(n) > 0 and f1(n) = Ω(g(n) and f2(n) = O(g(n)) then h(n) = Ω(g(n)
我是这样处理的：
f1(n) > c1*g(n) , for all n>n1; (*because f1(n) = Ω(g(n))*)
f2(n) < c2*g(n) , for all n>n2; (*beacuse f2(n) = O(g(n))*)
Thus, h(n) > c1*g(n) - f2(n) > c1*g(n) - c2*g(n) > (c1 - c2)*g(n), for all n>max(n1,n2)
现在的问题是，根据我的证明，h(n) = Ω(g(n)) 成立，c1 必须大于 c2，因为 O 和 Ω 符号中的常数必须是积极的。我无法消除这个前提。
谁能帮我解决这个问题。谢谢
我觉得这个说法不对。
设 g(n)=n、f1(n)=n+1、f2(n)=n 和 h(n)=2。
那么2 > 1 > 0成立，但是h(n)显然不是Ω(n).
我是这样处理的：
f1(n) > c1*g(n) , for all n>n1; (*because f1(n) = Ω(g(n))*)
f2(n) < c2*g(n) , for all n>n2; (*beacuse f2(n) = O(g(n))*)
Thus, h(n) > c1*g(n) - f2(n) > c1*g(n) - c2*g(n) > (c1 - c2)*g(n), for all n>max(n1,n2)
现在的问题是，根据我的证明，h(n) = Ω(g(n)) 成立，c1 必须大于 c2，因为 O 和 Ω 符号中的常数必须是积极的。我无法消除这个前提。
谁能帮我解决这个问题。谢谢
我觉得这个说法不对。
设 g(n)=n、f1(n)=n+1、f2(n)=n 和 h(n)=2。
那么2 > 1 > 0成立，但是h(n)显然不是Ω(n).