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

Question

Dove $ \ omega (f) $ indica il set di funzioni con F come limite inferiore, perché $ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $ ?

.
1. Come può la funzione a sinistra sia confrontata con un intero set?Pensavo di solito una funzione è un elemento del set, cioè $ G \ in \ omega (f) $ o non lo è, vale a dire $ G \ NOTIN \ OMEGA (F) $ .
2. se direbbe $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ \ \ \ \ \ sqrt (n} \ log_2n)$ Invece, non capirei ancora perché è vero.Come valuta il limite del lato sinistro?

Answer 1

Le notazioni $ f=omega (g) $ e $ f \ geq \ omega (g) $ < / span> sono identici. In entrambi i casi, significano che esiste una costante costante positiva $ c $ in modo tale da per grande $ N $ , $ f (n) \ geq cg (n) $ .

È possibile stimare la somma come segue: $$ \ 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). $$ Quest'ultima espressione è $ \ omega (n ^ {3/2} \ log ^ 2 n) $ , che è migliore di quello che rivendica.

Puoi anche stimare la somma da parte di un integrale. Secondo Wolfram Alpha, $$ \ int \ sqrt {x} \ log ^ 2 x \, dx=frac {2} {27} x ^ {3/2} (9 \ log ^ 2 x - 12 \ log x + 8) + c. $$ Dal momento che $ \ sqrt {i} \ log_2 ^ 2 I $ è in aumento, abbiamo $$ \ 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, $$ Da cui vediamo che la tua somma è $ \ theta (n ^ {n ^ ^ {3/2} \ log ^ 2 n) $ .