用大 O 符号比较 2 个函数

Question

问题是：

假设 f, g: N → N 是满足 f(n)=O(logn) 和 g(n) = Ω(nlogn) 的函数。 f(n) = Ω(g(n)) 是否可能？

我认为这是不可能的，因为 nlogn > logn，不确定这是不是真的，也不知道如何证明。

提前致谢！

Answer 1

不，这不可能。

让我们假设这是可能的：

• g(n) = Ω(nlogn) ==> 有 a 这样 g(n) > anlogn 对于足够大的 n.
• f(n) = Ω(g(n)) ==> 有 b 这样 f(n) > bg(n) > banlogn 对于足够大的 n.
• 让 c = ab ==> f(n) > cnlogn 足够大 n ==> f(n) = Ω(nlogn).
• f(n) = O(logn) ==> 有 d 这样 f(n) < dlogn 对于足够大的 n.
• ==> cnlogn < f(n) < dlogn ==> cnlogn < dlogn ==> n < d/c。这是不可能的，因为存在大于 d/c 的自然数 n。 ==> 与最初的假设相矛盾。