证明 f(n) = Θ(g(n)) 当且仅当 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

您可以从这里开始：

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，你需要从左边开始证明右边，然后从右边开始证明左边。

左 -> 右

我们认为：

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)).

类似于右 -> 左。

证明 f(n) = Θ(g(n)) 当且仅当 g(n) = Θ(f(n))

Prove that f(n) = Θ(g(n)) iff g(n) = Θ(f(n))

algorithm

proof

theorem-proving

big-theta