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

Question

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!

Answer 1

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!