big-o - 比较具有O表示法的2个函数

问题是 :

假设f，g:N→N是使得f(n)= O(logn)和g(n)=Ω(nlogn)的函数。
f(n)=Ω(g(n))可能吗？

我认为这是不可能的，因为nlogn> logn，不确定它是否正确，也不确定如何保存它。

提前致谢 !

最佳答案

不，不可能。

让我们假设这是可能的:

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。 ==>与最初的假设矛盾。