The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the total complexity for the two loops is O (N2)

Consider the following loop:

1. for i ← 1 to n      
2.  {  
3.          P (i)  
4.  }  

If the computation time t_i for ( P_I) various as a function of "i", then the total computation time for the loop is given not by a multiplication but by a sum i.e.

1. For i ← 1 to n      
2.  {  
3.             P (i)  
4.  }  

Takes 

If the algorithms consist of nested "for" loops, then the total computation time is

For i ← 1 to n
 {
      For j ←  1 to n       
    {
      P (ij)
    }
 }  

Example:

Consider the following "for" loop, Calculate the total computation time for the following:

1. For i ← 2 to n-1  
2.     {  
3.         For j ← 3 to i  
4.          {  
5.                        Sum ← Sum+A [i] [j]  
6.                  }  
7.             }  

Solution:

The total Computation time is:

4. While loop:

The Simple technique for analyzing the loop is to determine the function of variable involved whose value decreases each time around. Secondly, for terminating the loop, it is necessary that value must be a positive integer. By keeping track of how many times the value of function decreases, one can obtain the number of repetition of the loop. The other approach for analyzing "while" loop is to treat them as recursive algorithms.

Algorithm:

1. 1. [Initialize] Set k: =1, LOC: =1 and MAX: = DATA [1]  
2. 2. Repeat steps 3 and 4 while K≤N  
3. 3.  if MAX<DATA [k],then:  
4.     Set LOC: = K and MAX: = DATA [k]  
5. 4. Set k: = k+1  
6.    [End of step 2 loop]  
7. 5. Write: LOC, MAX  
8. 6. EXIT  

Example:

The running time of algorithm array Max of computing the maximum element in an array of n integer is O (n).

Solution:

1.    array Max (A, n)  
2. 1. Current max ← A [0]  
3. 2. For i ←  1 to n-1  
4. 3. do if current max < A [i]  
5. 4. then  current max ← A [i]  
6. 5. return current max.  

The number of primitive operation t (n) executed by this algorithm is at least.

1. 2 + 1 + n +4 (n-1) + 1=5n  
2. 2 + 1 + n + 6 (n-1) + 1=7n-2  

The best case T(n) =5n occurs when A [0] is the maximum element. The worst case T(n) = 7n-2 occurs when element are sorted in increasing order.

We may, therefore, apply the big-Oh definition with c=7 and n₀=1 and conclude the running time of this is O (n).