[解決済み] CLRSの相対的漸近成長に関する問題（表）の解き方について教えてください。

質問内容

最近微積分を習い、数学が得意なのに、この表を埋めるのに苦労しています。lim(n^k/c^n)をどう扱うかはその章で指定されているだけで、他の関数をどう比較すればいいのか全く分かりません。解答マニュアルを確認しましたが、それに関する情報はなく、答えが書かれた表があるだけで、ほとんど手がかりがありません。

解決方法は？

私はこの問題を解くとき、極限についてはあまり考えず、いくつかの事実とbig-O記法のよく知られた性質を頼りにしています。

事実1：すべての関数fとg、およびすべての指数p > 0について、f(n)=O(g(n))が成り立つのは、以下の場合のみである。 ^p = O(g(n)) ^p )、同様にo, ω, Θ, Θについてもそれぞれ同様です。これは定義から簡単に証明できます。定数cもp乗にすればいいだけです。

事実2：すべての指数ε > 0に対して、関数lg(n)はo(n) ^ε ). これは、l'Hôpitalの極限法則から導かれる：lim lg(n)/n ^ε = lim (lg(e)/n)/(ε n) ^ε-1 ) = (lg(e)/ε) lim n ^-ε = 0.

事実 3:

• f(n) ≦ g(n) + O(1) とすれば、2 ^f(n) = O(2 ^g(n) ).
• f(n) ≦ g(n) - ω(1)とすると、2 ^f(n) = o(2 ^g(n) ).
• f(n) ≧ g(n) - O(1) とすれば、2 ^f(n) = Ω(2 ^g(n) ).
• f(n) ≧ g(n) + ω(1) とすれば、2 ^f(n) = ω(2 ^g(n) ).

事実4：lg(n!) = Θ(n lg(n))です。証明はスターリング近似を用いる。

(a)を解くには、事実1を使って両辺を1/kの累乗にし、事実2を適用する。

(b)を解くには、nを書き換えます。 ^k = 2 ^lg(n)k で、c ⁿ = 2 ^lg(c)n となり、lg(c) n - lg(n) k = ω(1) であることを証明し、事実3を適用する。

(c)は特殊である。 ^sin(n) 0はo(√n)、nはω(√n)なので、これはNOの固まりである。

(d)を解くには、n≧n/2＋ω(1)であることを観察し、事実3を適用します。

(e)を解くには、nを次のように書き換えます。 ^lg(c) = 2 ^lg(n)lg(c) = 2 ^lg(c)lg(n) = c ^lg(n) .

(f)を解くには、事実4を用い、lg(n!) = Θ(n lg(n)) = lg(n) を求める。 ⁿ ).