# When using sigma notation, why is “1” put as value?

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!

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

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!

-
"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