If a function is linear (without any loops or recursions), the efficiency of that algorithm or the running time of that algorithm can be given as the number of instructions it contains. However, if an algorithm contains loops, then the efficiency of that algorithm may vary depending on the number of loops and the running time of each loop in the algorithm
Let us consider different cases in which loops determine the efficiency of an algorithm
Linear Loops
To calculate the efficiency of an algorithm that has a single loop, we need to first determine the number of times the statements in the loop will be executed. This is because the number of iterations is directly proportional to the loop factor. Greater the loop factor, more is the number of iterations. For example, consider the loop given below:
for(i=0;i<100;i++)
statement block;
Here, 100 is the loop factor. We have already said that efficiency is directly proportional to the number of iterations. Hence, the general formula in the case of linear loops may be given as
f(n) = n
However calculating efficiency is not as simple as is shown in the above example. Consider the loop given below:
for(i=0;i<100;i+=2)
statement block;
Here, the number of iterations is half the number of the loop factor. So, here the efficiency can be given as
f(n) = n/2
Logarithmic Loops
In logarithmic loops, the loop-controlling variable is either multiplied or divided during each iteration of the loop. For example, look at the loops given below
for(i=1;i<1000;i*=2) for(i=1000;i>=1;i/=2)
statement block; statement block;
Nested Loops
Loops that contain loops are known as nested loops. In order to analyse nested loops, we need to determine the number of iterations each loop completes. The total is then obtained as the product of the number of iterations in the inner loop and the number of iterations in the outer loop
In this case, we analyse the efficiency of the algorithm based on whether it is a linear logarithmic, quadratic, or dependent quadratic nested loop.
Linear logarithmic loop Consider the following code in which the loop-controlling variable of the inner loop is multiplied after each iteration. The number of iterations in the inner loop is log 10. This inner loop is controlled by an outer loop which iterates 10 times. Therefore, according to the formula, the number of iterations for this code can be given as 10 log 10.
for(i=0;i<10;i++)
for(j=1; j<10;j*=2)
statement block;
Quadratic loop In a quadratic loop, the number of iterations in the inner loop is equal to the number of iterations in the outer loop. Consider the following code in which the outer loop executes 10 times and for each iteration of the outer loop, the inner loop also executes 10 times. Therefore, the efficiency here is 100
for(i=0;i<10;i++)
for(j=0; j<10;j++)
statement block;
The generalized formula for quadratic loop can be given as f(n) = n2
Dependent quadratic loop In a dependent quadratic loop, the number of iterations in the inner loop is dependent on the outer loop. Consider the code given below:
for(i=0;i<10;i++)
for(j=0; j<=i;j++)
statement block;
In this code, the inner loop will execute just once in the first iteration, twice in the second iteration, thrice in the third iteration, so on and so forth. In this way, the number of iterations can be calculated as
1 + 2 + 3 + … + 9 + 10 = 55
.