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;
}
}
>Solution :
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
-
i = 0 , the inner for loop will run n times
-
i =1 ,the inner for loop will run n times.
-
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.