Time complexity in c (nested loop)-CodePudding

It is so hard for me to figure out time complexity of these 2 codes.

c = 0;
for (i = 0; i < n*n; i  ) 
for (j = 0; j < i; j  ) 
 c = c   1;

In the code above the outer loop's time complexity is n^2 , but it is hard to find in inner loop.

j = 1; c = 0;
for(i = 1; i <= n; i = i   1) { 
 for(k = 1; k <= j; k = k   1) { 
 c = c   1; 
 } 
j = j * 2; 
}

In the second code I thought the time complexity of outer loop is n and inner loop is 2^n. And I thought the multiple of these two ((n)*2^n) is the whole time complexity. Is it right? thank you for reading

CodePudding user response：

In the first code, you are iterating from 1 to n^2. This means you are iterations are 0, 1, 2, 3, ........n*n - 1. This series in AP.

 Sum of series in AP = N(N 1)/2 = n^2(n^2 1)/2
 Time Complexity is O(n^4)

In the second code, you are iterating from 1 to n. So, the inner loop will iterate accordingly 1, 2, 4,...2^n. This series is in GP

 Sum of series in GP = a(r^n-1)/r-1 = 2^n
 Time complexity is O(2^n)

CodePudding user response：

The first one has O(n^4), because of (n*n)^2. The second one has O(n * 2n)=O(n^2).