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.

Advertisements

Published by

Bobby Corpus

Loves anything related to Mathematics, Physics, Computing and Economics.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s