big-o - 用大 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 .这是不可能的，因为自然数 n存在大于 d/c . ==> 与最初的假设相矛盾。