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

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?
• Call $S_n$ the sum on the left. With the goal of computing the limits of $\frac{S_n}{n\sqrt{n}\log_2(n)}$ you apply Stolz-Cesaro theorem and try to compute the limit of $\frac{S_{n}-S_{n-1}}{n\sqrt{n}\log_2(n)-(n-1)\sqrt{n-1}\log_2(n-1)}=\frac{\sqrt{n}\log_2^2(n)}{n\sqrt{n}\log_2(n)-(n-1)\sqrt{n-1}\log_2(n-1)}$. The latter is $\infty$. Therefore, the original limit is also $\infty$. This tells you that for $n$ large enough $S_n\geq n\sqrt{n}\log_2(n)$. – plop Jul 28 '20 at 21:38
• Certainly in the class $\Omega(n\sqrt{n}\log_2(n))$ there are functions diverging faster than $S_n$. Maybe, just maybe, what they mean by the notation $\geq$ is the fact about the limit above being $\infty$. If so, it would be a confusing choice of notation. – plop Jul 28 '20 at 21:44
• You don't need to evaluate the limit. You just need to lower-bound it: consider sum $\sum_{i=n/2}^n$. – Dmitry Jul 28 '20 at 21:45
• Limits are always easier than a concrete inequality, since they are an inequality quantified by an existential quatifier. – plop Jul 28 '20 at 21:50

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)$$.
• Thanks! What about the notation $f\in\Omega(g)$? I thought $\Omega(g)$ denotes a set, specifically the set of functions that grow faster than $g$. – timtam Jul 29 '20 at 8:57
• But am I right that $\Omega(g)$ is a set? So mathematically, the notation $f=\Omega(g)$ is wrong, but it is a conventional notation in CS? It is really confusing to me because on one side of the equation you have a function and on the other you have a set – timtam Jul 29 '20 at 12:05
• The definition is: $f = \Omega(g)$ (or: $f$ is $\Omega(g)$) if there exists $C>0$ such that $f(n) \geq Cg(n)$ for all large enough $n$. Sometimes you also encounter $\Omega(g)$ inside an expression, such as $h + \Omega(g)$. This means "$h + f$ for some $f$ which is $\Omega(g)$". – Yuval Filmus Jul 29 '20 at 13:12
• @david The usage of = for $O,\Omega,\Theta$ classes is a common 'abuse of notation': a shorthand that usually yields no problems as long as its consistently used. See also $O$ is not a function, so how can a function be equal to it?. – Discrete lizard Jul 30 '20 at 14:03