Time Complexity when Loop Variable Depends upon Outer Loop Variable

Question

What is the time complexity of the following piece of code in worst case?

s = 0;
for( i = 1; i <= n; ++i ) {
 for( j = 1; j <= i * i; j++ ) {
 for( k = 1; k <= j and j % i == 0; k++ )
 s++;
 }
}

Each loop depend on the outer loop variable. How should I proceed in such a case?

The innermost loop will run only occasionally, so how can I evaluate this case?

For every increment of i middle loop runs i^2 times. For every iteration of middle loop, I'm not able to calculate how many times the innermost loop will run in terms of the outer loop.

I think innermost loop iterates for i times. The middle loop runs for j = 1 to i^2 and j % i != 0 is in i cases and for other i cases, j % i = 0. As inner loop runs for j % i == 0 it would be iterated i times.

Now for the times the innermost loop runs i times, the middle loop runs i^2 times and the outer loop runs i times, I think the complexity is n^4.

• Dan Pichelman: Is Problems Calculating Big-O Complexity relevant? (It's been a long time since I studied this)
• user40980: @AshishPani we don't have latex or mathjax on the site. When you start wanting to write that sort of notation, it becomes a question for computer science stack exchange instead as its moved far away from the design and architecture type questions that is the focus of this site.
• amon: This question is not a duplicate, and is on-topic here. But please show how you have tried to calculate the Big-O! Questions work much better when you show what you've done to solve the problem yourself, instead of asking other people to do all the work for you.
• Dan Pichelman: Also possibly relevant: What is O(...) and how do I calculate it?
• amon: This question has been greatly improved :) I'll be happy to write an answer when it gets reopened.

Answer 1

While the end result is correct, I wouldn't accept what is written in the question as an answer, because I can't really see how it gets to the answer.

The innermost loop: There are two cases. If j % i ≠ 0 then it iterates once, if j % i = 0 then it iterates j times.

The middle loop: Given i, it iterates i^2 times. The value of j will range from 1 to i^2. There are i cases j = i, j = 2i, j = 3i, ..., j = i^2 where j % i = 0, and i^2 - i cases where j % i ≠ 0. The inner loop will iterate once (i^2 - i) times. The inner loop will iterate j times when j = i, j = 2i, j = 3i, ..., j = i^2. The total number of iterations is the sum of (t * i) for 1 ≤ t ≤ i, which is i * (i - 1)/2 * i which is about i^3 / 2. The other cases only involved i^2 - i operations and can therefore be ignored. Summary: Given i, the middle loop performs about i^3 / 2 operations.

The outer loop: i ranges from 1 to n. There are i^3 / 2 operations for each iteration. So the total number of operations is the sum of (i^3 / 2) for i = 1 to n, which is about i^4 / 8.