Some people were not amused by the title of the previous post. It was in a way misleading. So I’m now going to give an appropriate title to this post, albeit a rather boring title.

In this article, let’s try to count the number of times the “Hello World” is printed by the code snippet below:

for(int i=0;i<10;i++){ for(int j=0;j<i;j++){ for(int k=0;k<j;k++){ System.out.println("Hello World"); } } }

Let’s try to count for the first few values of i,j and k.

1,1,1 ----> 1 2,1,1 ----> 1 + 2 2,2,1 2,2,2 3,1,1 ----> 1 + 2 + 3 3,2,1 3,2,2 3,3,1 3,3,2 3,3,3 4,1,1 ----> 1 + 2 + 3 + 4 4,2,1 4,2,2 4,3,1 4,3,2 4,3,3 4,4,1 4,4,2 4,4,3 4,4,4

Looking at the pattern above, you can see that when i=1, the “Hello World” is printed only once. When i=2, it is executed 1 + 2 = 3. When i=3, it is executed 1 + 2 + 3 = 6 times, and when i=4, it is executed 1 + 2 + 3 + 4 = 10 times. So how many times is the statement executed when i=5? Based on the pattern we can see that it will be executed 1 + 2 + 3 + 4 + 5 times.

However, what we are after is the sum of the number of executions from i=1 to i=10. If we denote by the total number of executions, we can write this mathematically as:

From the previous post we know that

Hence, we have

Multiplying out the summand we have

Distributing the summation:

Let’s simplify this expression for a general

We know that the second summation is equal to

The first summation is the sum of squares of the first n numbers. To evaluate this, let’s tackle the sum of cubes (*):

You might be wondering how we arrived at the right-hand side. If you write the summation explicitly, say for n=5, the right-hand side looks like:

Going back to the right-hand side, let’s expand it to get:

Canceling the term containing the and solving for the , we get:

The last term is just equal to . Plugging this value and simplifying we get:

This finally gives us

Using this expression in the value of gives us:

Substituting n=10, we get the total number of executions for the “Hello World”, which is

.

There is a much easier way of solving this which we shall cover in the next post.

* See this page for more information on the sum of squares of the first n numbers.