Let n be a power of 2.
int sum = 0;
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < n; j )
sum = 1
Is the time complexity O(N) or O(nlogn). Thanks!
CodePudding user response:
So first of all, it isn't necessary to know what kind of number is n is, since the asymptotic complexity is dependent of any arbitrary n(as long it is a positive integer).
We also know that the inner loop will do n iterations, hence we can denote the inner loop the time complexity of O(n)
.
About the outer loop. We know that at each iteration we double the values of i
. Since i
isn't zero at the initialization, it will for sure be increased by it doubling it. Since we are actually doubling i
at each iteration we know that we reach n with exponentially increasingly larger iteration steps(for i=1, 2, 4, 8, 16, 32, 64, 128...). Hence the number of steps to reach n will become smaller while we get closer to it. Now knowing this we see that we are doing at most log(n) iterations to reach n.
Why? -> Well this might be mathematically informal, but I hope this is fine. In order to compute the number of iterations, one has to solve this equation: 2^x = n, where x is the number of iteration. We can see this basically by the explanation above. At each iteration step we double i until we reach n. The solution for x is than: x < log_2(n)
Hence the time complexity of the outer loop is O(log(n))
.
Know this, one can simply multiply the complexities to O(log(n)n)
.