1
$\begingroup$
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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – gnasher729
    Feb 7 at 8:36
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Feb 7 at 10:20
  • 2
    $\begingroup$ 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? $\endgroup$ Feb 7 at 14:21

1 Answer 1

5
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.