For Loops and Finite Series

At the request of one of my AP Computer Science students, I’m posting a few solutions to a simple loop problem in Java. The question reads:

How many times are the following loops executed?

for(int i=0; i<10; i++)
   for(int j=0; j<i; j++)
      System.out.println(i*j);

The possible options are A) 100, B) 20, C) 10, or D) 45.

Now, there are a few ways you can go about solving this problem. The easiest is to simply plug this excerpt into a Java program and execute it. Add line numbers if you don’t want to count, and you’ll easily see how many times the statement is executed.

You can also work it out by hand using simple arithmetic. A for-loop of the form

for(int i=0; i<n; i++)

will execute n times. Extending this further, a nested for-loop from i=0 to 10, j=0 to 10 will execute 10 x 10 = 100 times. Since the upper bound on the inner loop changes on every iteration, we cannot compute this with a single multiplication. When i=0 in the outer loop, the inner loop never executes (0 is not less than 0). When i=1, the inner loop executes once for j=0. When i=2, the inner loop executes twice, for j=0 and j=1. Extending this for the variable boundary (i < j) case, we compute the number of iterations as follows:

A more elegant approach, mathematically speaking, uses our knowledge of finite series to re-write the above series and find its solution:

There ya have it, folks! Three different ways to determine how many times a loop is executed, ranging from brute force to elegant.