Time complexity of Iterative programs.

About graph: f(n) is the actual time taken by the Algorithm, but in practice, we say it the time taken by the program to exist but when you write it into a program and execute it, we found out that this is not the real-time, it is just an approximation. It means, if f(n) increases for the algorithm, then the program time increases if f(n) decreases program time decrease. 

To find out f(n), we need to know that there are 2 types of algorithm:

Iterative: Here there is no function calling and having for loops and all, then it is iterative.

Recursive: Here there is a function calling itself then it is called recursion.

Any program that can be written using iteration could be written using recursion and any recursion program can be converted into an iteration. So both are equivalent in power. But if we go through analysis, both are different:

In order to analyze an iterative program, we need to count the number of times a loop is getting executed. Whereas, if we have to find out the time taken by the recursive program, we use recursive equations which means, we write a function of in terms of n/2

A(n)->f(n).

A(n)->f(n/2) 

In case the algorithm does not contain Iteration or Recursion means there’s no depending on running time on the I/P size, means whatever is the input size, the running time is going to be a constant value.

So if there’s no Iteration or Recursion in the algorithm, we need not worry about the time, it will be constant for such program we write the order of 1 O(1) which represents constant time.   

Examples:  

 //Example 1:  
 int timecomp(int n)  
 {  
   int i;  
   for(i=0; i<n; i++)  
     printf("RavelingTech"); //this line will be printed n times  
 }  
 //Therefore, the time complexity of the algorithm is O(n).  
 

//Example 2:  
 int timecomp(int n)  
 {  
   int i,j;  
   for(i=0; i<n; i++)  
   {  
     for(j=0; j<n; j++)  
       printf("RavelingTech"); //this line will printed nxn times  
   }  
 }  
 //Therefore, the time complexity of the algorithm is O(n^2).  
 

//Example 3:   
 int timecomp(int n)  
 {  
   int i=1, s=1;  
   while(s <= n)  
   {  
     i++;   //increment in i is linear  
     s=s+i;  //increment in s depends on i  
     printf("RavelingTech");  
   }  
 }  
 /*  
 s | 1 3 6 10 15 21 ........n  
 i | 1 2 3 4 5 6 ........k  
 By the time i reaches to k, s will be the sum of 1st k natural number  
   = k(k+1)/2  
 Now, if the loop has to stop , then  
 k(k+1)/2 > n  
 k = O(√n) <--- Time Complexity.  
 */