What is the time complexity of the following code segment?

Question

I need help to determine what the time complexity of a code segment.

I've tried to understand how to add everything up but I'm not sure it is correct. The first loop and second loop is to my understanding logarithmic and the last is linear, or atleast that is what I think. But I don't understand how to finalise the problem and provide a time complexity.

sum = 0; count = 0;
for (int i = 1; i < N; i = i*2){
    sum = sum + 1;
    for (int j = i; j < N*N; j = j*2){
        count++;
    }
    for (int k = i; k < N; k++){
        count--;
    }
}

My guess is that it is: (logN * logN) + (logN * N) -> O(NlogN) But since the third loop is not nested in the second loop I'm not sure how to properly determine the complexity. So please help me.. :)

The final answer is correct, although your reasoning is ... imprecise. Also since they are not nested you can treat them as if they were each in a separate instance of the outer loop. — meowgoesthedog
Okey, so the final answer is O(NlogN). Thanks for the clarification! As I said I'm not that sure how to get there, since this was just a wild guess based on the fact that I can remove low-order terms etc. — Anteman

Leandro Caniglia Leandro Caniglia · Accepted Answer · 2019-01-07T13:23:16

Assume first N=2^M. Then M = lg(N).

The outer loop runs for i = 2^0, 2^1, 2^2, ..., 2^(M-1). A total of M steps.

The first inner loop runs for j = 2^s, ..., 2^(M + M - 1) in step s (out of Msteps). Total 2M-s.

The second runs for k = 2^s, 2^s + 1, ..., 2^M - 1 in step s. Total 2^M - 2^s.

The first loop takes a total of (2M-0) + (2M-1) + ... + (2M - (M-1)) which is O(M^2) = O(lg(N)^2).

The second (2^M-2^0) + ... + (2^M-2^(M-1)), which equals M2^M - 2^M + 1, which is O(M2^M) = O(Nlg(N)).

Therefore the total complexity is O(lg(N)lg(N)) + O(Nlg(N)) = O(Nlg(N)).

For the general case, where N is not a power of two, consider M such that 2^M < N < 2^(M+1) and conclude that the complexity remains O(Nlg(N)).

What is the time complexity of the following code segment?

1 Answers