1
$\begingroup$

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?
Improve this question
$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – plop Jul 28 '20 at 21:38
  • $\begingroup$ 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. $\endgroup$ – plop Jul 28 '20 at 21:44
  • $\begingroup$ You don't need to evaluate the limit. You just need to lower-bound it: consider sum $\sum_{i=n/2}^n$. $\endgroup$ – Dmitry Jul 28 '20 at 21:45
  • $\begingroup$ Limits are always easier than a concrete inequality, since they are an inequality quantified by an existential quatifier. $\endgroup$ – plop Jul 28 '20 at 21:50
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – timtam Jul 29 '20 at 8:57
  • $\begingroup$ This notation isn't commonly used in technical papers, at least not in areas I am aware of. $\endgroup$ – Yuval Filmus Jul 29 '20 at 9:14
  • 1
    $\begingroup$ 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 $\endgroup$ – timtam Jul 29 '20 at 12:05
  • $\begingroup$ 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)$". $\endgroup$ – Yuval Filmus Jul 29 '20 at 13:12
  • 1
    $\begingroup$ @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?. $\endgroup$ – Discrete lizard♦ Jul 30 '20 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.