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.

BryanH
  • 281
  • 5
  • 8
Ashish Pani
  • 133
  • 4
  • 2
    Is [Problems Calculating Big-O Complexity](http://programmers.stackexchange.com/q/186802/64132) relevant? (It's been a long time since I studied this) – Dan Pichelman Oct 26 '15 at 18:31
  • 1
    While it is very likely that we have a duplicate of this question, I disagree that [Big-O for nested loop](http://programmers.stackexchange.com/q/110605/64132) is the duplicate. Big-O has an inner loop that always executes `n` times; this question has the inner loop execution be a function of the outer loop value. – Dan Pichelman Oct 26 '15 at 18:34
  • no of updates to s is to be denoted in Big O like we do for no of comparisons in sorting. – Ashish Pani Oct 26 '15 at 18:34
  • polynomial time – Ewan Oct 26 '15 at 18:41
  • 1
    How? If polynomial then n^3 or n^4 or what? – Ashish Pani Oct 26 '15 at 18:43
  • 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. –  Oct 26 '15 at 18:45
  • Could you rewrite the code to just be a sequence of nested loops,i.e. merge the middle loop with the if condition so that s is still updated the same # of times but it may be easier to count how often s is incremented? – JB King Oct 26 '15 at 18:49
  • 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?](http://programmers.stackexchange.com/q/132331/64132) – Dan Pichelman Oct 26 '15 at 19:02
  • There are clearly two cases, either j % i == 0 or j % i != 0. In one case the loop iterates 0 times, in the other case j times. When is j % i == 0? And this question is absolutely not a duplicate. The title is a duplicate, but not the question. – gnasher729 Oct 27 '15 at 00:11
  • i think innermost loop iterates for i times. Middle loop run 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 run for j%i==0 it would be iterated i times. – Ashish Pani Oct 27 '15 at 04:46
  • Now as innermost loop run for i times,middle loop run for i^2 times and outer loop run for i times , I think complexity would be n^4 – Ashish Pani Oct 27 '15 at 04:53
  • 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 Answers1

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.

gnasher729
  • 42,090
  • 4
  • 59
  • 119