Feyman Technique

Feynman Technique of learning new things, involves four steps to master any concept. They are: 

1. Learn the concept & gain the best understanding of it 

2. Teach the concept to someone, even if it is to imaginary students

3. Re-learn the concept if you find yourself unable to explain it clearly

4. Finally, Simplify the concept further using simple language and day-to-day analogies to solidify your and your students understanding of them.

More on it here....

Learn anything in four steps

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$)

Measuring the efficiency of a Algorithm

Algorithms, despite the scary sounding word, are nothing more than a series of steps or actions that are performed to accomplish a certain task, in the world of computers.

Like in real world, each task can be accomplished by a different set of steps, with each set making different sense in terms of time or ease of accomplishment. For instance, if you know a certain location or mall has a coffee shop somewhere, and you want to get there, then there are two sets of steps you can engage in to accomplish that:

1. First set of steps, involve the obvious, which is to walk/drive to that location and walk-around looking for that coffee shop. Or,
2. Second steps, involve using a GPS app on your phone or ask someone who is familiar with that location, where the coffee shop is and go there straight.

Now, the first set of steps obviously require more time unless you happen to be super lucky. It does not guarantee that you will be efficient every time (every time you employ it, for a different location that is) and in most cases require a lot more time than second set of steps where you walk straight to the shop, thanks to your GPS. Same task, different steps

Similarly, accomplishing a task using different algorithms involve different set of steps and in most cases vary in efficiency similar to searching around for a coffee shop vs using GPS. It therefore, becomes vital that we use some technique to measure the efficiency of different algorithms, and employ the right one for the right situation. This is the reason, why we should measure efficiency at all.

However, in some scenarios different algorithms employed, similar to different steps employed won't yield much different results at all. For instance finding a coffee shop, among 3 shops down the block wont be much different whether you walk and look for it.

However, it will be much different if you are looking for a coffee shop among a relatively big city block, with 100's of shops, isn't it ? Well, it will be, and if it is not obvious already that our first way of haplessly searching would be a terrible and inefficient, our friend or someone will definitely sooner or later will advise us to use our GPS, or look it up for us. This points us to the fact that an algorithms efficiency is truly only measured relative to how well it can handle large data.

So any measure of an algorithm, needs to be expressed in terms of how well it can handle growth of input data, similar to how efficient using a GPS to find a coffee shop will function in a mega city vs a small town.

At the very least, measuring an efficiency of a algorithm involves measuring the number of steps that need to be performed to accomplish the result. For instance, if we are looking for a value in a array:

int[] arr = new int[]{12,3,4,7,8,3,3,9,6};
int lookingFor = 6;
for(int i=0;i<=arr.length;i++)
{
    if(lookingFor = arr[i])
    {
      System,out.printlin(" Found " + lookingFor + " in " + i + " steps");
    }
}

This above code executes and finds "6", in 9 attempts, which is the size of the array.It compares each element against "6", until it finds it at the end of the array.

So if we employ this algorithm, to find a value, "v" in a array of "n" elements, then it can be said that this algorithm, has an efficiency of O(n). Big O, is a convention that is used to express algorithm efficiency very similar to the use of f($x^2$) in mathematics.


Different algorithms, have different efficiency values, with some better than others for the same task. Here are some of the common efficiency values along with the most common scenarios that will result in that efficiency.

Efficiency	Common scenarios
O(1)	Anything which gets completed in constant time, no matter what the size of data is
O(n)	Anything which requires at the most, 1 full parse of all the data elements
O($n^2$)	Anything which requires going over the data multiple times (of n). Typically this involves nested-loops, where  the inner loop parses all data elements, for each iteration of outer loop, which itself iterates n times, where n is the size of data
O(log $2^n$)	Anything which involves repeatedly dividing the data into two halves to find the result. Examples are binary tree search, or recursive calls.

In addition, there are other rules of common sense, such as ignoring smaller values of n, and constants which are minuscule for large sets of data.

I will expand more on this in future, with examples of how to measure efficiency, and different comparisons between techniques.