Por que $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ ômega (n \ sqrt {n} \ log_2n) $?

Question

onde $ \ ômega (f) $ denota o conjunto de funções com f como limite inferior, por que é $ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ ômega (n \ sqrt {n} \ log_2n) $ ?

.
1. Como a função pode ser comparada a um conjunto inteiro?Eu pensei que geralmente uma função é um elemento do conjunto, ou seja, $ g \ in \ ômega (f) $ ou não é, ou seja, $ g \ notin \ ômega (f) $ .
2. se diria $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ ômega (n \ sqrt {n} \ log_2n)$ Em vez disso, eu ainda não entenderia por que é verdade.Como você avalia o limite do lado esquerdo?

Answer 1

as notações $ f=ômega (g) $ e $ f \ geq ímega (g) $ < / span> são idênticos. Em ambos os casos, eles significam que existe uma constante positiva $ c $ tal que para grande $ n $ , $ f (n) \ GQ CG (n) $ .

Você pode estimar a soma da seguinte maneira: $$ \ 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). $$ A última expressão é $ \ ômega (n ^ {3/2} \ Log ^ 2 n) $ , o que é melhor do que você reivindica.

Você também pode estimar a soma por uma integral. De acordo com Wolfram Alpha, $$ \ int \ sqrt {x} \ log ^ 2 x \, dx=frac {2} {27} x ^ {3/2} (9 \ log ^ 2 x - 12 \ log x + 8) + c. $$ Desde a $ \ sqrt {i} \ log_2 ^ 2 i $ está aumentando, nós temos $$ \ 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, $$ a partir do qual vemos que sua soma é $ \ theta (n ^ {3/2} \ log ^ 2 n) $ .