Saturday, February 6, 2016

Measuring Nested loop efficiency

In my earlier post regarding Algorithm efficiency, which can be found here, I discussed what is a algorithm, why is measuring its efficiency important and finally ended it with some of the simplest ways to measure the efficiency of a algorithm.

In this post, we expand on the concept further examining how to measure the efficiency of a algorithm that involves the most commonly encountered scenario, while coding: Nested loops

What are nested loops anyway ?
Nested loops is simply a loop within an other loop. The inner loop is executed one time, for each iteration of the outer loop. So if the outer loop is to execute k times, this means the inner loop is set to execute k times. Now if the inner loop itself is meant to execute a block of code m times, then that block of code is executed m times, for every iteration of the outer loop. Since we know the outer loop iterates k times, the block of code is ultimately executes k x m times.

Citing an example, have a look at this code with nested loops:

int loopCount = 0;
int k = 5, m= 3;
for (int i=0;i<k;i++) //outer loop executing 5 times, since k=5 
{
  System.out.println("Outer loop iteration " + i+1);
 for(int n=0;n<m;n++) //inner loop executing 3 times, since m=3
 {
    loopCount++;
    System.out.print(loopCount+",");
 }
}

Output:
Outer loop iteration 1
1,2,3
Outer loop iteration 2
4,5,6
Outer loop iteration 3
7,8,9
Outer loop iteration 4
10,11,12
Outer loop iteration 5
13,14,15

Since the outer loop is set to execute 5 times, and for each one of those iterations the inner loop executes 3 times, ultimately the inner most block of code executes 5 x 3 = 15 times.

Now, what is the efficiency of this algorithm ?

If we were to consider, the innermost block of code in the inner most loop as a single step in our algorithm, and repeating it a certain number of times will bring us closer to accomplishing the task (such as searching, sorting ) our algorithm is set out to accomplish, then the efficiency of that algorithm is nothing more than how many times, that innermost core block of code is repeated.

With that said, if for a set of data of size n, if the outer loop executes n times, and the inner loop executes n times, then the total number of times the inner most block of code, which formulates our step in algorithm is executed n x n = $n^2$ times. Therefore our algorithms efficiency is O($n^2$)

What are some of the most common scenarios in nested-loop algorithm execution ?

While repeated execution of the inner block, $n^2$ times is common, there are other scenarios where the pattern looks slightly different.

For instance, if we were to calculate the sum of all factorials less than or equal a given number, that is to accomplish this, for a value of 4:

                         result =  4! + 3! + 2! = 1!

a rudimentary(= not the most efficient way) code block involves the inner loop executing 1 less number of times every time, leading to a code block like this:

int result = 0, currentFactorial=1;
int k = 4;
for (int i=k;i>0;i--) //outer loop executing 4 times
{
 for(int n=1;n<=i;n++) //inner loop executing 1 less time 
 {
   currentFactorial = currentFactorial * n;
 }
 result = result + currentFactorial;
}
System.out.print("result = " + result);

if we analyze the above block of code, it will result in executing the inner most block of code "currentFactorial = currentFactorial * n;"  in a  pattern like this:

When i=4
 currentFactorial = currentFactorial * n; executed 4 times

When i = 3
 currentFactorial = currentFactorial * n; executed 3 times

When i=2
 currentFactorial = currentFactorial * n; executed 2 times

When i = 1
 currentFactorial = currentFactorial * n; executed 1 times

So in scenarios like this, the inner most block of code is executed in a pattern of 4,3,2,1 a handy formula can be utilized to calculate the efficiency of the algorithm. That is:

             For a data set  of n, the inner most block of code is repeated

                      n + (n-1) + (n-2) + ..... + (n-n) times 

            and the resulting sum of the number of times, it is repeated is

                            = $${n(n+1)} /{2}$$

An other common pattern that you will likely encounter is, for instance, for a value of 4, the pattern goes something like 3,2,1. That is

 For a data set  of n, the inner most block of code is repeated

                      (n-1) + (n-2) + ..... + (n-n) times 

            and the resulting sum of the number of times, it is repeated is

                            = $${n(n-1)} /{2}$$

Applying, the simple rules of measuring algorithm efficiency, mentioned in my earlier post on algorithm efficiency, which instructs use to ignore constants and lower order terms, the efficiency of a block of code that executes either $${n(n+1)} /{2}$$ times or $${n(n-1)} /{2}$$ is O($n^2$)

VR180 to 3D SBS Converter