下述关于O(n)的结论是否正确：a(n)=O(b(n))与b(n)=O(a(n))能否同时成立

首先明确大O记号的标准定义：

对于定义域为正整数的非负函数 f(n) 和 g(n)，f(n) = O(g(n)) 成立当且仅当存在正实常数 α 和正整数阈值 n₀，使得所有满足 n ≥ n₀ 的项，都有 f(n) ≤ α · g(n)。

按照这个定义，两个大O关系同时成立不仅不矛盾，本身就是渐近记号中 Θ(·) 的定义：如果 a(n) = O(b(n)) 和 b(n) = O(a(n)) 同时满足，我们就称 a(n) = Θ(b(n))，意思是两个函数渐近同阶。

举个最直观的例子验证：

• 取 a(n) = n，b(n) = 2n + 10
  1. 证明 a(n) = O(b(n))：取 α=1，n₀=1，对所有 n ≥1，都有 n ≤ 1·(2n+10)，满足定义
  2. 证明 b(n) = O(a(n))：取 β=3，n₀=10，对所有 n ≥10，都有 2n+10 ≤ 3n，满足定义

完全符合要求，没有任何逻辑冲突。

额外补充：你的教授大概率是混淆了大O和小o记号。如果是 a(n) = o(b(n)) 和 b(n) = o(a(n))，确实不可能同时成立：小o代表严格的渐近上界，要求 limₙ→∞ a(n)/b(n) = 0，反过来就要求这个极限是无穷，二者无法同时满足。

内容的提问来源于stack exchange，提问作者Dan