2017-10-29 18 views
-1

以下の質問は宿題として与えられます。私はそれを解決しようとどんなに困難になったとしても、私は解決策に達することができませんでした。問題は、与えられた関数aが、set-little(b)の要素であるかどうかを調べる。複雑な小文字の証拠

show that n^(ln(ln(ln(n)))) is o(ceiling(ln(n))!) 

興味深いのは、階乗演算子!nの隣が、ceiling(ln(x))にだけではなく、次のではないです。

これはちょっとしたステートメントなので、限界を使って解決しなければならないと思います。私は階乗演算子の配置について何を言うべきか分からない。

+0

ln n = o(n)ので

、そのln(ln n) = o(ln n)等、従ってダミーラベルf(n) = o(n)を以下'lim(n-> inf)[f(n)/ g(n)] = 0'である。これを試してみることはできますか? – Miraj50

+0

私はこれが解決する方法であることを知っています。しかし、私はf(n)/ g(n)の限界が0であることを証明することができませんでした。それが私が助けを求めるところです。それを解決する別の方法がある場合は、私もそれを知りたいと思います。 – ugar

+0

スターリング近似を使用して階乗を確認し、拡大したい限界を書き始めます。 –

答えて

0

のは、いくつかの未知のf(n)として漸近記法を書いて、両辺の対数(ベース - nを)取ることから始めましょう:

最後のステップへの第二のアップが、丸みを帯びたという事実から、次の
ln(ln(ln n))) = f(log(n, ceil(ln n)!)) 
       = f(ln(ceil(ln n)!)/ln n) [logarithm rules] 
       = f([ ceil(ln n) ln(ceil(ln n)) - O(ln n) ]/ln n) [Stirling] 
       = f((1 + O(1)) ln(ln n + O(1)) - O(1)) 
       = f(ln(ln n)) 

数値の値は常に1より小さい(明らかに非常に小さい量であり、漸近的に無視することができる)。 `F(N)= O(G(N)) '=>場合

n^ln(ln(ln n))) = o(ceil(ln n)!)

関連する問題