# Questions concerning $\Omega$ and $\Theta$

How do I solve this: $\displaystyle\sum_{k = 1}^n \frac{k}{3}$ is $\Omega(n^2)$? I know that the summation would be $\displaystyle\sum\limits_{k=1}^n \dfrac{n^2+n}{6}$, but how do I solve $\displaystyle\sum\limits_{k = 1}^n \frac{k}{3}$ is $\Omega(n^2)$?

Also how do I solve $\sum\limits_{j = 1}^n\sum\limits_{k=1}^n 7n$ is $\Theta(n^3)$? Does anyone know any good website explaining these type of problems?

-
Your sums seem to be miswritten. Can you clarify what you mean by $\sum_{i=1}^n k/3$? –  Ian Coley Mar 26 '13 at 4:06
sorry i will fix that –  user1688953 Mar 26 '13 at 4:11
Your fourth sum could use some work, unless there's just supposed to be a $1$ there. –  Julien Clancy Mar 26 '13 at 4:36
thanks, just fixed it –  user1688953 Mar 26 '13 at 4:50
Are you sure it's correct now? As it's written, the sum is in fact not Theta of $n^2$. –  Julien Clancy Mar 26 '13 at 5:56

## 1 Answer

You're right in that $\sum_1^n \frac{k}{3} = \frac{n^2 + n}{6}$. Recall that $f \in \Omega(g)$ if there are some $c > 0$ and $x_0$ with $f(x) > cg(x)$ for all $x > x_0$. Intuitively, $f$ is $\Omega(g)$ if $g$ bounds $f$ below. In this case you can just take $c = \frac{1}{6}$, assuming $n > 0$. The strategy here is simply to find the right constant.

Recall that $f \in \Theta(g)$ if there are $c, C > 0$ and $x_0$ with $cg(x) < f(x) < Cg(x)$ for all $x > x_0$, or equivalently if it is both $O(g)$ and $\Omega(g)$. You can pick up the computability part from here.

-
thanks, sorry i did a mistake on the second question for theta, I corrected it right now –  user1688953 Mar 26 '13 at 4:50
do you know any website where I can learn how to do these types of questions? –  user1688953 Mar 26 '13 at 5:10
I don't know any websites that have this, but there's a very good elementary book called Algorithm Design by Kleinberg and Tardos that I used for my algorithms class. It has a really nice, illustrative section about big-O notation. If you google it, you should be able to fine either a copy or excerpts. –  Julien Clancy Mar 26 '13 at 5:56