DSA DAY 04

Time Complexity 
======================================================

1) for(int i =0; i<n; i++){   ---> n+1 times 
      stmt;                   ---> n times 
}
time complexity = O(n)
==========================================================

2) for(int i =n; i>0; i--){   ---> n+1 times 
      stmt;                   ---> n times 
}
time complexity = O(n)
===========================================================

3)  for(int i =1; i<n; i=i+2){   ---> n+1 times 
      stmt;                      ---> n/2 times 
}
time complexity = O(n)
=============================================================

4) for(int i=0; i<n;i++){        --->n+1 times
       for(int j =0;j<n;j++){    --->n*(n+1) times 
         stmt;                   ---> n*n times 
}
}
time complexity =  O(n^2)
=============================================================

5) for(int i=0; i<n;i++){        
       for(int j =0;j<i;j++){    
         stmt;                  
}
}
Explantion 1+2+3+...+n = n*(n+1)/2 = n^2+1/2 
time complexity =  O(n^2)
==============================================================

6) p=0;
  for(int i=1; p<=n; i++){
     p=p+i;
}
assume p>n stopping criteria 
p=k(k+1)/2 >n
k^2>n
k> root n 
time complexity = O(root n)