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.

First of all, I never really learned exactly what Sigma notation is, and although I understand the basics, there are some things that are confusing me. I'm trying to convert the following algorithm to a sum so that I can find the time complexity:

for i <- 1 to n do
    for j <- 1 to n do
        for k <- i + j to 2n do
            print(i, j, k)

Now I've been studying my professor's notes quite hard, and I've come up with the following: $$\sum\limits_{i=1}^n\sum\limits_{j=1}^i\sum\limits_{k=i+j}^{2n}c$$

However, in one of his (smaller) examples he put the following: $$\sum\limits_{i=1}^n\sum\limits_{j=1}^i1$$ where 1 was used instead of a value c. What is the difference between this?

Also, how should I get started on simplifying this? I am having difficulty getting started.

To clarify, I do not want the final answer, as I'm trying to learn what is happening here. Thanks!

share|improve this question
    
$c=1$ in this case. –  Alex Becker Jan 30 '13 at 7:05
    
@Yep I'm not sure I understand your question. Are you asking if letting $c=1$ in the first formula yields the second formula and if the answer is yes, how? –  Git Gud Jan 30 '13 at 7:12
    
@GitGud: I guess the question you just asked helped me out a bit in any case. The problem is that I didn't even know how the second formula could work if it is 1, since there's nothing to plug the values into to get the summation, right? I think I'm epically confused. –  Yep Jan 30 '13 at 7:15
add comment

1 Answer

up vote 4 down vote accepted

First of all, a brief intro to sigma notation:

$$ \sum_{i=1}^n f(i)= f(1)+f(2)+f(3)+\ldots+f(n) $$ The notation just represents a finite sum of some quantity that depends (or perhaps doesn't depend) on some integer index (i.e. variable) $i$. In your case, you are using it to count loop operations. Take a simple example with a single for loop:

for i=1:n
  i
end

The program performs exactly 1 operation during each loop. So, to count operations, we just need to add up the number $1$ $n$ times - the complexity is $\sum_{i=1}^n 1=n$. Now consider a slightly different loop:

for i=1:n
  a=1+3*i;
end

Now, for each $i$ we are performing 2 operations - one addition and one multiplication (not counting say, memory overhead which would be negligible). So, to find the complexity, we need to add up the number $2$ exactly $n$ times: $\sum_{i=1}^n 2$. This is a different value of "$c$" corresponding to a different number of operations. Now, consider one more loop:

for i=1:n 
  i^i
end

Here, we are multiplying $i$ by itself $i$ times. So, the number of operations is no longer constant - it changes with each go through the loop. Now the complexity would look like $\sum_{i=1}^n i=1+2+3+\ldots+n$

Hope this helps, and good luck in your course!

share|improve this answer
    
"we just need to add up the number 1 $n$ times" – PERFECT. This is what I was missing. Thank you so much! –  Yep Jan 30 '13 at 7:20
add comment

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.