なぜ$ \ sum_2 ^ 2I \ GEQ \ OMEGA（n \ sqrt {n} \ log_2n）$ですか？

Question

ここで、 $ \ omega（f）$ は、fを持つ関数のセットを下限として、なぜ $ \ \ \ \ \ \ \ \ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ GEQ \ OMEGA（n \ sqrt {n} \ log_2n）$ ？

1. 左側の機能をセット全体と比較することができますか？私は通常、関数はセットの要素、つまり $ g \ inωinmega（f）$ 、つまり $ g \ notin \ omega（f）$ 。
2. $ \ sum_2 ^ 2i \ in \ sqrt {i} \ omega（n \ sqrt {n} \ log_2n）$ 代わりに、私はそれが真実である理由を理解していません。左側の制限をどのように評価しますか？

Answer 1

表記 $ f=omega（g）$ と $ f \ geq \ ommga（g）$ < / SPAN>は同じです。どちらの場合も、大きな $ n $ のための正の定数 $ c $ が存在することを意味します。 、 $ f（n）\ geq cg（n）$ 。

次のように合計を見積もることができます。 $$ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2 i \ geq \ sum_ {i= n / 2} ^ n \ sqrt {i} \ log_2 ^ 2 i \ geq \ sum_ {i= n / 2} ^ n \ sqrt {n / 2} \ log_2 ^ 2（n / 2）\ geq \ frac {n} {2} \ cdot \ sqrt {n / 2} \ log_2 ^ 2（n / 2）。 $$ 後者の式は $ \ ommega（n ^ {3/2} \ log ^ 2 n）$ です。これは、請求するものよりも優れています。

積分で合計を推定することもできます。 Wolfram Alphaによると、 $$ \ int \ sqrt {x} \ log ^ 2 x \、dx=frac {2} {27} x ^ {3/2}（9 \ log ^ 2 x - 12 \ log x + 8）+ C $$ $ \ sqrt {i} \ log_2 ^ 2 i $ が増えているので、 $$ \ int_0 ^ n \ sqrt {x} \ log ^ 2 x \、dx \ leq \ sum_ {i= 1} ^ n \ sqrt {i} \ log ^ 2 i \ leq \ int_1 ^ {n + 1} \ sqrt {x} \ log ^ 2 x \、dx、 $$ あなたの合計が $ \ thetaであることがわかります（n ^ {3/2} \ log ^ 2 n）$