¿Por qué $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ ^ ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $?

Question

donde $ \ omega (f) $ denota el conjunto de funciones con f como un límite inferior, ¿por qué es $ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ onga (n \ sqrt {n} \ log_2n) $ ?

1. ¿Cómo se puede comparar la función a la izquierda con un conjunto completo?Pensé que generalmente una función es un elemento del conjunto, es decir, $ g \ in \ omega (f) $ o no lo es, es decir, $ G \ Notin \ Omega (F) $ .
2. Si diría $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ ^ 2i (n \ sqrt {n} \ log_2n)$ en su lugar, todavía no entendería por qué es verdad.¿Cómo evalúa el límite del lado izquierdo?

Answer 1

Las Notaciones $ F=Omega (G) $ y $ f \ geq \ omega (g) $ < / span> son idénticos. En ambos casos, significan que existe que existe un constante positivo $ C $ de modo que para gran $ n $ , $ f (n) \ geq cg (n) $ .

Puedes estimar la suma de la siguiente manera: $$ \ 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). $$ La última expresión es $ \ omega (n ^ {3/2} \ log ^ 2 n) $ , que es mejor de lo que reclame.

También puede estimar la suma por parte de una integral. Segú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. $$ Desde $ \ sqrt {i} \ log_2 ^ 2 i $ está aumentando, tenemos $$ \ 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, $$ desde donde vemos que su suma es $ \ theta (n ^ {3/2} \ log ^ 2 n) $ .