Pourquoi $ \ Sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $?

Question

où $ \ oméga (f) $ désigne l'ensemble des fonctions avec F comme limite inférieure, pourquoi est $ \Sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $ ?

1. Comment la fonction de gauche peut-elle être comparée à un ensemble complet?Je pensais généralement une fonction est un élément de l'ensemble, c'est-à-dire $ g \ \ \ \ oméga (f) $ ou ce n'est pas, c'est-à-dire $ g \ notin \ omega (f) $ .
2. si cela dirait $ \ sommant {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ omega (n \ sqrt {n \ \ log_2n)$ à la place, je ne comprendrais toujours pas pourquoi c'est vrai.Comment évaluez-vous la limite du côté gauche?

Answer 1

Les notations $ f=oméga (g) $ et $ f \ geq \ oméga (g) $ < / span> sont identiques. Dans les deux cas, ils signifient qu'il existe une constante positive $ C $ tel que pour le grand $ n $ , $ f (n) \ geq cg (n) $ .

Vous pouvez estimer la somme comme suit: $$ \ 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). $$ Cette dernière expression est $ \ oméga (n ^ {3/2} \ log ^ 2 n) $ , ce qui est meilleur que ce que vous prétendez.

Vous pouvez également estimer la somme d'une intégrale. Selon Wolfram Alpha, $$ \ int \ sqrt {x} \ journal ^ 2 x \, dx=frac {2} {27} x ^ {3/2} (9 \ journal ^ 2 x - 12 \ log x + 8) + C. $$ Depuis $ \ sqrt {i} \ log_2 ^ 2 i $ augmente, nous avons $$ \ int_0 ^ n \ sqrt {x} \ journal ^ 2 x \, dx \ leq \ sum_ {i= 1} ^ n \ sqrt {i} \ journal ^ 2 i \ leq \ int_1 ^ {n + 1} \ sqrt {x} \ log ^ 2 x \, DX, $$ Dès que nous voyons que votre somme est $ \ theta (n ^ {3/2} \ log ^ 2 n) $ .

.