比較2個功能與大O符號

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 < dlogn ==>n < d/c。這是不可能的，因爲存在大於d/c的自然數n。 ==>與最初的假設相矛盾。