证明f（n）=Θ（g（n））且g（n）=Θ（f（n）） [英] Prove that f(n) = Θ(g(n)) iff g(n) = Θ(f(n))

问题描述

我遇到了这个问题：

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

我发现此语句的所有内容均无效。例如，我遇到过一个州的答案：

Everything I have found points to this statement being invalid. For example an answer I've come across states:

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.

我了解我的确切问题与所发现的示例之间存在细微差异，但我只能提出无法证明这一点的解决方案。我认为这无法得到证明是正确的，还是我正在仔细研究某些细节？

I understand that there are slight differences between my exact question and the examples I have found, but I've only been able to come up with solutions that do not prove it. I am correct in thinking that it is not able to be proved or am I looking over some detail?

推荐答案

您可以从这里开始：

形式定义：f（n）=Θ（g（n））表示存在正常数c1，c2和k，使得对于所有整数0≤c1g（n）≤f（n）≤c2g（n） n≥k。

Formal Definition: f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k.

因为您有 iff ，所以需要开始从左侧开始并证明右侧，然后从右侧开始并证明左侧。

Because you have that iff, you need to start from the left side and to prove the right side, and then start from the right side and prove the left side.

左->右

我们认为：

f(n) = Θ(g(n))

，我们想证明

g(n) = Θ(f(n))

因此，我们有一些正常数 c1 ， c2 和 k 使得：

So, we have some positive constants c1, c2 and k such that:

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），我们得到：

If we combine (1) and (2), we obtain:

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

如果您考虑 c3 = 1 / c2 和 c4 = 1 / c1 ，它们存在且为正（因为分母为正）。对于所有 n≥k 都是如此（其中 k 可以相同）。

If you consider c3 = 1/c2 and c4 = 1/c1, they exist and are positive (because the denominators are positive). And this is true for all n ≥ k (where k can be the same).

因此，我们有一些正常数 c3 ， c4 ， k 这样：

So, we have some positive constants c3, c4, k such that:

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

，这意味着 g （n）=Θ（f（n））。

类似于右->左。

这篇关于证明f（n）=Θ（g（n））且g（n）=Θ（f（n））的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！