Can someone please explain how this is O(n^2) I am not sure how they got this answer

for(i = 0; i < n; i  ){
   if (a[i] > b[i]){
      print(a[i]-b[i]);
   }
   else{
      print(b[i]-a[i]);
   }
}
for(i = 0; i < n; i  ){
   for(j = 0; i < n; j  ){
      c[i][j] = 0;
    }
}

CodePudding user response：

Time complexity can be calculated by calculating the order of iterations. in the code that you have shared

//1
    for(i = 0; i < n; i  ){ // o(n)  
       if (a[i] > b[i]){
          print(a[i]-b[i]);
       }
       else{
          print(b[i]-a[i]);
       }
    }
//2
    for(i = 0; i < n; i  ){   // o(n) 
       for(j = 0; i < n; j  ){ //  o(n)
          c[i][j] = 0;
        }
    }

Now when

1. i = 0 , the inner for loop will run n times

2. i =1 ,the inner for loop will run n times.

3. i = n-1, the inner for loop will run n times

Therefore inner for loop will run n times for each value of i ( from 0 to n-1 ). therefore the time complexity is o(n*n)

The total time complexity is o(n^2) ( from 2 for loop ) o(n) ( from 1st for loop ) since o(n^2) dominates o(n) , we consider only the highest power of n.

CodePudding user response：

The O(n^2) complexity come from the last iteration,

for(i = 0; i < n; i  ){
   for(j = 0; i < n; j  ){
      c[i][j] = 0;
    }
}

It iterates n times for i. and for each iteration of i, j is iterated n time, making nxn iteration, hence O(n^2).

Edit : in big-O notation, We only take fastest-growing order in account. O(n!)>O(exp(n))>O(n^m)>O(n^p) (m>p>1) >O(n)>O(log n).