# Big-O time complexity for this code snippet

public void m1(int n) {
sum = 0;
for (int i = n/2; i <= n; i++) {
for (int j = 1; j <= n; j = 2 * j) {
for (int k = 1; k <= n; k = k * 2) {
sum++;
}
}
}
}


So, I know that the innermost loop and second loop are $$\log(n)$$ and the outermost loop is essentially $$O(n)$$, so that means $$O(n\log(n)\log(n))$$. But I am lost on what to do next. I am between $$O(n^2 \log(n))$$ and $$O(n \log^2(n))$$. Can someone tell me which is right and explain why?

• So what is n (log n) (log n)? Don’t you trust yourself enough to figure this out? What about using a spreadsheet and evaluating all three expressions for n=1 to 100? Feb 7 at 8:36
• Both of them are right. $O(n \log^2 n) \subset O(n^2 \log n)$. Also, $O(f(n))$ denotes a set of functions so it does not make sense to say that a "a loop is $O(n)$". You are probably referring to the number of iterations of the loop. Feb 7 at 10:20
• The question is whether $n \log(n) \log(n) = n^2 \log(n)$ or $n \log(n) \log(n) = n \log^2(n)$. First, this question is off-topic for a computer science site. Second, you need to do your own homework before asking a math site, have you reviewed your high school math book or asked a friend? Feb 7 at 14:21

## 1 Answer

You are right, the two innermost loops perform $$\Theta(\log n)$$ iterations each, so we have a total of $$\Theta(\log^2 n)$$ iterations, which are repeated $$\Theta(n)$$ times in the outer loop, which implies that we have a total of $$\Theta(n\log^2 n)$$ iterations.

You just have to multiply the number of iterations of each loop since they are nested and all the iterations are performed without interruptions (we just increase a variable inside the loop). So we can not only give an upper-bound ($$O(n\log^2 n)$$ ) but also a lower-bound ($$\Omega(n\log^2 n)$$), which implies a complexity of $$\Theta(n\log^2 n)$$.