Prove that 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.

我知道我的问题与我找到的例子之间存在细微差别，但我只能想出不能证明它的解决方案。请问我是否正确认为无法证明，还是我忽略了一些细节？

- user3068177

---

O和Theta不是同一个概念。请查阅它们含义上的区别。 - Ctx

请注意，n = O(n)，n = O(n^2)，但 n^2 != O(n)。这个简单的例子可以帮助您忽略一些不好的例子（比如 f(n) = O(g(n)) implies g(n) = O(f(n))，这可能是正确的，但只适用于某些特定情况）。 - ROMANIA_engineer

“f(n) = O(g(n))的意思是g(n)增长比f(n)快” - 这是错误的。粗略地说，它意味着g至少以与f同样的速度增长。 - user2357112

https://dev59.com/cnRB5IYBdhLWcg3w6LV3%CE%98n-and-on - user3068177

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

右边类似于左边。

- ROMANIA_engineer