Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

Question

Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

1. How can the function on the left be compared to a whole set? I thought usually a function is an element of the set, i.e. $g\in\Omega(f)$ or it is not, i.e. $g\notin\Omega(f)$.
2. If it would say $\sum_{i=0}^n\sqrt{i}\log_2^2i \in \Omega(n\sqrt{n}\log_2n)$ instead, I still would not understand why it is true. How do you evaluate the limit of the left side?

Answer 1

The notations $f = \Omega(g)$ and $f \geq \Omega(g)$ are identical. In both cases, they mean that there exists a positive constant $C$ such that for large $n$, $f(n) \geq Cg(n)$.

You can estimate the sum as follows: $$ \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). $$ The latter expression is $\Omega(n^{3/2} \log^2 n)$, which is better than what you claim.

You can also estimate the sum by an integral. According to Wolfram alpha, $$ \int \sqrt{x} \log^2 x \, dx = \frac{2}{27} x^{3/2} (9\log^2 x - 12 \log x + 8) + C. $$ Since $\sqrt{i} \log_2^2 i$ is increasing, we have $$ \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, $$ from which we see that your sum is $\Theta(n^{3/2} \log^2 n)$.