2

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.

  • 2
    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
  • 2
    @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
  • 3
    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
  • 2
    Also possibly relevant: What is O(…) and how do I calculate it? – Dan Pichelman Oct 26 '15 at 19:02
  • 2
    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
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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