復發關係和漸近複雜性

Question

我想了解f(n) = n^cos n和g(n) = n的復發關係。我被告知，這種關係沒有與大O，小O，大歐米加，小歐米茄或Theta有關的漸近行爲。有關cos n的振盪？我能否對這種行爲有更多的瞭解？

當我在我的計算器上使用L'醫院規則時，我得到undefined。

Answer 1

函數n ^{cos n}是O（n）。由於-1 ≤ COSÑ≤ 1，函數n ^COSÑ總是N的有界^-1和n ，所以特別是它總是由O（N）的上界。然而，這不是Ω（N），因爲任何數n 任何常數c，你可以找到N>ň其中n ^COSň < CN。要做到這一點的一種方法是尋找n的選擇，其中cos n是負的; n的值爲^{- ＆epsilon;任何＆epsilon的};對於任何c，> 0將最終小於cn。

希望這會有所幫助！