# Time Complexity when Loop Variable Depends upon Outer Loop Variable

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.

• Is Problems Calculating Big-O Complexity relevant? (It's been a long time since I studied this) – Dan Pichelman Oct 26 '15 at 18:31
• @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. – user40980 Oct 26 '15 at 18:45
• 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. – amon Oct 26 '15 at 19:00
• Also possibly relevant: What is O(…) and how do I calculate it? – Dan Pichelman Oct 26 '15 at 19:02
• This question has been greatly improved :) I'll be happy to write an answer when it gets reopened. – amon Oct 27 '15 at 23:50