# Some More Counting Techniques

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 $C$ the total number of executions, we can write this mathematically as:

$\displaystyle C = \sum_{i=1}^{10} \sum_{j=1}^i j$

From the previous post we know that

$\displaystyle C = \sum_{j=1}^i j = \frac{i(i+1)}{2}$

Hence, we have

$\displaystyle C = \sum_{i=1}^{10} \frac{i(i+1)}{2} = \frac{1}{2}\sum_{i=1}^{10} i(i+1)$

Multiplying out the summand we have

$\displaystyle C = \frac{1}{2}\sum_{i=1}^{10} ( i^2 + i )$

Distributing the summation:

$\displaystyle C = \frac{1}{2}\Large(\sum_{i=1}^{10} i^2 + \sum_{i=1}^{10} i\Large)$

Let’s simplify this expression for a general $n$

$\displaystyle C = \frac{1}{2}\Large( \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i \Large)$

We know that the second summation is equal to

$\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

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

$\displaystyle \sum_{i=0}^{n} i^3 = \sum_{i=0}^{n} (i+1)^3 - (n + 1)^3$

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:

$\displaystyle \sum_{i=0}^{5} (i+1)^3 - (5 + 1)^3 = (0+1)^3 + (1+1)^3 + (2+1)v + (3+1)^3+ (4+1)^3 + (5+1)^3 - (5 +1)^3$
$\displaystyle = 1^3 + 2^3 + 3^3 + 4^3 +5^3 = \sum_{i=0}^{5} i^3$

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

$\displaystyle \sum_{i=0}^{n} i^3 = \sum_{i=0}^{n} (i^3 + 3i^2 + 3i +1) - (n+1)^3$
$\displaystyle = \sum_{i=0}^{n} i^3 + 3 \sum_{i=0}^{n} i^2 + 3 \sum_{i=0}^{n} i + \sum_{i=0}^{n} 1 - (n+1)^3$

Canceling the term containing the $i^3$ and solving for the $\sum_{i=0}^{n} i^2$, we get:

$\displaystyle 3\sum_{i=0}^{n} i^2= (n+1)^3 - 3\sum_{i=0}^{n} - \sum_{i=0}^{n} 1$

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

$\displaystyle 3\sum_{i=0}^{n} i^2 = n^3 + 3n^2 +3n + 1 - 3\frac{n(n+1)}{2} - n - 1$
$\displaystyle = n^3 + 3n^2 + 2n - \frac{3n^2 - 3n}{2}$
$\displaystyle = \frac{2n^3 + 6n^2 + 4n - 3n^2 - 3n}{2}$
$\displaystyle = \frac{2n^3 + 3n^2 + n}{2}$
$\displaystyle = \frac{n(2n^2 + 3n + 1)}{2} = \frac{n(n+1)(2n+1)}{2}$

This finally gives us

$\displaystyle \sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

Using this expression in the value of $C$ gives us:

$\displaystyle C = \frac{1}{2} \Bigg( \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i\Bigg)$
$\displaystyle C = \frac{1}{2} \Bigg( \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\Bigg)$
$\displaystyle = \frac{1}{6} n(n+1)(n+2)$

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

$\displaystyle C = \frac{1}{6} 10 \times 11 \times 12 = 220$.

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.