I have this question for a homework assignment.

Consider the following algorithm segment:

    for i=1 to n
       for j=i to n

What is the number of additions (+) performed by this code segment? Prove your answer.

It clearly wants you to create and solve a recurrence relation based on this algorithm although I have no idea how to convert the algorithm into a recurrence relation that can then be solved.

I know that the first for loop (i) will run (n-1) times, but I don't understand how to generalize how many times the second for loop will run given that it will run a different number of times each time the first loop runs given that i will have been incremented.

I'm not looking for a solution to this question but rather the method for converting this type of algorithm, into a general case that can then be calculated.


I'm assuming the limits are inclusive of $1$ and $n$(you might want to use $n-1$ instead). [Not relevant to the counting, but note that $X$ is not initialized.]

The iterative nature of the algorithm is naturally representable in tabular form, recursive relation is not necessary unless your homework explicilty asks for one. Each line below lists out all the values $j$ takes for every iteration of the outer loop. Each time $j$ takes a value from $i$ upto $n$(or $n-1$ if you use that as the limit) there is an addition.

When $i=1$: $j$ takes values $1,2,3...n$ for a total of $n$ additions.

When $i=2$: $j$ takes values $2,3...n$ for a total of $n-1$ additions.



When $i=n$: $j$ takes the value $n$ for a total of 1 addition.

That should be enough to figure out the total.

for i = 1 to n
   for j = i to n
      x = x + 5;

So here, the outer loop runs $(n-1+1) = n$ times.
For each iteration of outer loop inner loop also iterates from i to n.

Thus, to calculate total number of additions, we've to calculate the number of times inner loop has been iterated. And it is as follows:

i = 1
   j = 1 -> n
i = 2
   j = 2 -> n
i = (n-1)
   j = (n-1) -> n

Summing up we'll get:
$$(n-1) + (n-2) + \dots + 2 + 1 = $$ $$\frac{(n-1)[(n-1)+1]}{2} = \frac{n(n-1)}{2}$$

And rest you can solve.

Also, if you want to see more on a computer's perspective then it should also be kept in mind that each iteration requires one addition.
For example, this code segment in C++ can be written as:

for (int i = 1; i <= n; i++)
   for (int j = 1; j <= n; j++)
      x += 5;

Here, at each iteration one addition is also there (i++ and j++).
In such a case except that answer, there will also be same number of additions in the j loop and also $n$ additions in i loop. So, final answer would be:
$$\frac{n(n-1)}{2} + \frac{n(n-1)}{2} + n = $$ $$n(n-1)+n = n^2.$$

  • $\begingroup$ You seem to have calculated $\sum_{i \le j} i^2$ rather than $\sum_{i \le j} i$. The correct answer is $\frac{n(n+1)}2$. $\endgroup$ – DanielV Mar 2 '17 at 20:47
  • $\begingroup$ Yeah, this answer is incorrect I spoke to my professor about it. $\endgroup$ – TheSaint321 Mar 3 '17 at 3:17
  • $\begingroup$ @TheSaint321 please see the first line of the second paragraph of your question. That was indeed the reason why I did that. Even I was thinking about your question. $\endgroup$ – Mayank M. Mar 3 '17 at 5:53
  • $\begingroup$ @Mayank Yeah, I was wrong in my interpretation of the question. Just want to make sure that future people with this type of problem don't read this question and take your answer as accurate given that DanielV and Akay's answers were correct. I appreciate you trying to help though and apologize for the confusion. $\endgroup$ – TheSaint321 Mar 3 '17 at 6:01
  • 1
    $\begingroup$ The solution obviously has an upper bound of $n^2$. Your solution is $n^3$, far beyond that, so sorry no downvote removal. You can delete your answer and it will remove the downvote from your score though. If you correct your answer and ping me here I will remove the downvote. $\endgroup$ – DanielV Mar 3 '17 at 16:31

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.