computer-science - 需要帮助理解这个证明（计算机科学）

Question

我不明白提出这个反例有什么意义。它不满足 () = (())，因为 () 不是 (())。() = ω(()) 如果 f(n) 是 2n 并且 g(n) 是 n。

那么简单地“让（）= 2和（）=。”如何有效？?

标签： computer-scienceproof

Answer 1

但是对于 g(n) = n，f(n) = 2n 是 O(g(n))。令 n0 = 1 和 c = 3。然后：

f(n) = 2n <= 3n = 3 * n = c * n = c * g(n), for n >= n0

因此，反例是有效的。