[Solved] Can anybody explain the time complexity of this code? [closed]

Question

So basically you have two loops, the top one is quite simple, but the second one is a tad bit more tricky.

for (i = n/2; i < n; i) // ~n/2 so O(n)
    for(j = 0; j < n; j = 2 * j) // How many times does this run for n

So j doubles after every iteration until we reach n, so if we double n, j will only do one extra iteration! Alternatively, you could say that log_2 n is how many times we can double j to reach n.

So the time complexity is O(n log n).

Accepted Answer

So basically you have two loops, the top one is quite simple, but the second one is a tad bit more tricky.

for (i = n/2; i < n; i) // ~n/2 so O(n)
    for(j = 0; j < n; j = 2 * j) // How many times does this run for n

So j doubles after every iteration until we reach n, so if we double n, j will only do one extra iteration! Alternatively, you could say that log_2 n is how many times we can double j to reach n.

So the time complexity is O(n log n).