we're all know that for a code snippet like
for(int i=0;i<n;i++){ //do something}
Has a complexity of O(n) and we can find it:
sum symbol from n=0 to n-1 c1 = c1* ((n-1)*n)/2
What if the code will be :
for(int i=0;i<n;i+=2){ //do something}
I dont only interested in with big o notation but also,exact growth rate function.
Is there anyone to help me ? thanks in advance
The //do something shall be executed n/2 times .
Hence complexity = O(n/2) = O(n) (same as the previous loop)
Practically obviously the second loop will take less time as it only executes half the number of statements. However as n grows, the growth in time complexity shall be linear for both the loops.
for(int i=0;i<n;i++) { /* do something */ }
It has unknown complexity where we don't know about /* do something */. If the loop's body hasn't inner loops based on n. It has complexity O(n).
for(int i=0;i<n;i+=2) { /* do something */ }
As same as above, this has complexity O(n) too. Note that O(n/2) = O(n).
When you take Big O notation , we assume n is a positive set .
N can grow in 2 ways 1-Linearly 2-Exponentially
N grows exponentially if we multiply n by an integer >1. Consider the code snippet
for(i=1;i<n;i=i*2){
}
here n increase by a large value, i.e, 2,4,8,16,32....
N grows linearly if we increment n by an integer>0( The code that you gave grows linearly )
For linear growth, Time complexity is O(n)
For exponential growth, Time complexity is O(logn)
Lets consider another example
for(i=0;i<n*10;i++){//has Complexity O(n)
}
for(i=0;i<n*n;i++){//has Complexity O(n*n)
}
This is because 10 is a constant and n is not a constant
