证明f(n)=Θ(g(n))iff g(n)=Θ(f(n))

Question

我遇到了问题:

f(n) are asymptotically positive functions. Prove f(n) = ?(g(n)) iff g(n) = ?(f(n)). 

我发现的一切都表明这个陈述是无效的.例如,我遇到的答案是:

f(n) = O(g(n)) implies g(n) = O(f(n))
f(n) = O(g(n)) means g(n) grows faster than f(n). It cannot imply that f(n) grows
faster than g(n). Hence not true.

另一个州:

 If f(n) = O(g(n)) then O(f(n)). This is false. If f(n) = 1 and g(n) = n 
 for all natural numbers n, then f(n) <= g(n) for all natural numbers n, so
 f(n) = O(g(n)). However, suppose g(n) = O(f(n)). Then there are natural
 numbers n0 and a constant c > 0 such that n=g(n) <= cf(n) = c for all n >= 
 n0 which is impossible.

我理解我的确切问题和我找到的例子之间存在细微差别,但我只能提出不能证明这一点的解决方案.我认为它无法被证实或者我正在查看一些细节,这是正确的吗？

Answer 1

你可以从这里开始:

形式定义:f(n)=Θ(g(n))表示存在正常数c1,c2和k,因此对于所有n≥k,0≤c1g(n)≤f(n)≤c2g(n) .

因为你有这个iff,你需要从左侧开始并证明右侧,然后从右侧开始并证明左侧.

左 - >右

我们认为:

f(n) = ?(g(n))

我们想要证明这一点

g(n) = ?(f(n))

因此,我们有一些积极的常数c1,c2而k这样的:

0 ? c1*g(n) ? f(n) ? c2*g(n), for all n ? k

f和之间的第一个关系g是:

c1*g(n) ? f(n)     =>     g(n) ? 1/c1*f(n)    (1)

f和之间的第二个关系g是:

f(n) ? c2*g(n)     =>     1/c2*f(n) ? g(n)    (2)

如果我们结合(1)和(2),我们得到:

1/c2*f(n) ? g(n) ? 1/c1*f(n)

如果你考虑c3 = 1/c2和c4 = 1/c1,它们存在并且是积极的(因为分母是积极的).这对所有人来说都是如此n ? k(k可以是相同的).

因此,我们有一些积极的常数c3,c4,k使得:

c3*f(n) ? g(n) ? c4*f(n), for all n ? k

这意味着g(n) = ?(f(n)).

类似于右 - >左.