how do i find the time complexity (big O) of this triple loop?

Question

for (int i = 0; i < n^2; i++) {
  for (int j = 1; j < i; j = 2j) {
    for (int k = 0; k < j; k++) {
      System.out.println("x");
    }
  }
}

My thoughts are that the outer loop is n^2, middle loop is log(n) and inner loop is n so that means the total time complexity is O(n^3 * log(n)) but I'm not sure if this is right.

Answer 1

The complexity of the following nested loop:

for (int i = 0; i < n^2; i++) {
  for (int j = 1; j < i; j = 2j) {
    for (int k = 0; k < j; k++) {
      System.out.println("x");
    }
  }
}

...is O(⁴):

The value of n is only used in n^2, so let's define m=n^2

The first two iterations of the outer loop do nothing (the j-loop condition is immediately false), so we can start at 2 instead of 0.

The print statement is an O(1) operation, so the inner loop is O().

We can then write the code like this:

for (int i = 2; i < m; i++) {
  for (int j = 1; j < i; j = 2j) {
    O(j)
  }
}

Now let's rewrite the j-loop defining p as log(j) (all logarithms here have base 2):

for (int i = 2; i < m; i++) {
  int q = ceil(log(i))
  for (int p = 0; p < q; p++) {
    O(2^p)
  }
}

the inner loop's complexity represents a geometric sum so it has a closed formula, and we can rewrite:

for (int i = 2; i < m; i++) {
  int q = ceil(log(i))
  O(2^q)
}

The loop's body will have repeatedly the same value for q for some different values of i until i overtakes the next power of 2. We could introduce a variable q equal to ceil(log(i)), which makes its own iterations:

for (int q = 1; q <= ceil(log(m)); q++) {          
  for (int i = 2^(q-1) + 1; i <= 2^q && i < m; i++) {
    O(2^q)
  }
}

As the value of i doesn't matter anymore for the inner loop, we can use its number of iterations as a coefficient for the big Oh expression:

for (int q = 1; q <= ceil(log(m)); q++) {
  O(2^(q-1) * 2^q)
}

To be fair, the condition i < m would limit the number of iterations of the previous inner loop when the outer loop is in its last iteration, but asymptotically this is not significant.

We can simplify:

for (int q = 1; q <= ceil(log(m)); q++) {
  O(4^q)
}

Which is again a geometric sequence, summing up to:

O(4^log())

= O([2^log()]²)

= O(²)

= O(⁴)