Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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