CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
Henry Zhu
Henry Zhu

Reputation: 9

What is the time complexity (big-O) of the following code? It is hard to analyze

int cnt = 0;
for (int i = 1; i < n; i++) {
  for (int j = i; j < n; j++) {
    for (int k = j * j; k < n; k++) {
      ++cnt;
    }
  }
}

I have no idea of it. How to analyze the time complexity of it?

Upvotes: 0

Views: 139

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58399

It's easy to see that the code is Omega(n²) (that is, is at least quadratic) - the two outer loops execute around n²/2 times.

The inner k loop executes zero times unless j is less than sqrt(n). Even though it executes zero times, it takes some computation to compute the conditions for the loop, so it's O(1) work in these cases.

When j is less than sqrt(n), i must also be less than sqrt(n), since by the construction of the loops, j is always greater than or equal to i. In these cases, the k loop does n-j² iterations. We can construct a bound for the total amount of work in this inner loop in these cases: both i and j are less than sqrt(n), and there's at worst O(n) work done in the k loop, so there's at most O(n²) (ie: sqrt(n) * sqrt(n) * n) total work done in the inner loop.

There's also at most O(n²) total work done for the cases where the inner loop is trivial (ie: when j>sqrt(n)).

This gives a proof that the runtime complexity of the code is θ(n²).

Methods involving looking at nested loops individually and constructing big-O bounds for them do not in general give tight bounds, and this is an example question where such a method fails.

Upvotes: 2

Related Questions