¿Por qué $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ ^ ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $?
-
29-09-2020 - |
Pregunta
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) $ ?
- ¿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) $ .
- 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?
Solución
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) $ .