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!

  • $\begingroup$ $c=1$ in this case. $\endgroup$ – Alex Becker Jan 30 '13 at 7:05
  • $\begingroup$ @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? $\endgroup$ – Git Gud Jan 30 '13 at 7:12
  • $\begingroup$ @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. $\endgroup$ – 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

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

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 

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!

  • $\begingroup$ "we just need to add up the number 1 $n$ times" – PERFECT. This is what I was missing. Thank you so much! $\endgroup$ – Yep Jan 30 '13 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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