Почему $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $?

Question

Где $ \ Omega (f) $ обозначает набор функций с f как нижний границ, почему $ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $ ?

1. Как функция слева может сравниться с целым набором?Я думал, что обычно функция - это элемент множества, т. Е. $ g \ in \ Omega (f) $ или нет, то есть $ g \ notin \ omega (f) $ .
2. Если бы это скажем $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ omagega (n \ sqrt {n} \ log_2n)$ вместо этого я все еще не пойму, почему это правда.Как вы оцениваете предел левой стороны?

Answer 1

Обозначения $ f=Omega (g) $ и $ f \ geq \ omega (g) $ < / span> идентичны. В обоих случаях они означают, что существует положительная константа $ C $ Такое, что для большого $ n $ , $ f (n) \ geq cg (n) $ .

Вы можете оценить сумму следующим образом: $$ \ 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). $$ Последнее выражение составляет $ \ Omega (n ^ {3/2} \ log ^ 2 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. $$ Поскольку $ \ sqrt {i} \ log_2 ^ 2 i $ увеличивается, у нас есть $$ \ 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, $$ Из которого мы видим, что ваша сумма - $ \ Theta (n ^ {3/2} \ log ^ 2 n) $ .