sum = 0;
for (int i = 1; i <= n; i++ )
    for (int j = 1; j <= i*i; j++)
        if (j % i ==0)
            for (int k = 0; k < j k++)

I am trying to find out time complexity of this above program.

First "for loop" will run n times.

Second for loop will execute overall n^3 times

The innermost loop will execute when j is multiple of i, that will happen exactly i times.

Please help me to find the overall time complexity of this program.

  • 1
    $\begingroup$ This is not a recursive program. $\endgroup$ – adrianN Aug 29 '17 at 14:20
  • $\begingroup$ oh sorry! it's iterative program $\endgroup$ – Manu Thakur Aug 29 '17 at 14:24
  • $\begingroup$ Please do not use images when you could use text instead. $\endgroup$ – Tom van der Zanden Aug 29 '17 at 14:24
  • $\begingroup$ Your question already contains the start of a good answer; but you just stop in the middle. Why did you get stuck? What are you uncertain about? $\endgroup$ – Tom van der Zanden Aug 29 '17 at 14:25
  • $\begingroup$ sure, no it's not duplicate of that question. $\endgroup$ – Manu Thakur Aug 29 '17 at 14:26

The number of times that the if statement is executed is $$ \sum_{i=1}^n i^2 = \Theta(n^3). $$ The number of times that sum is incremented is $$ \sum_{i=1}^n \sum_{j'=1}^i ij' = \sum_{i=1}^n i \sum_{j'=1}^i j' = \sum_{i=1}^n \Theta(i^3) = \Theta(n^4). $$ Here $j' = j/i$, and the reason we are allowed to do this is that the inner loop gets executed only when $j'$ is integral.

We get that overall, the running time is $\Theta(n^4)$.

| cite | improve this answer | |

The rule to calculate time complexity is to measure how many times (at most) will your code run compared to input. in our case, we have the input as n

the outermost loop runs n times, so this loop has a complexity of O(n), assuming code inside this loop is static.

Then comes next level, a loop that explicitly run n2 times, that makes an O(n2) piece of code.

Then we have an if block, that would have a complexity _O(1) because it would not scale on n size

and finally, a loop that runs j times; j has an upper bound of n2 , that should make the inner most loop of O(n2)

That makes the overall complexity = n × n2 × n2 = n5 i.e. O(n5) not O(n4)

| cite | improve this answer | |
  • $\begingroup$ While $O(n^5)$ is true, an even better upper bound is $O(n^4)$. $\endgroup$ – Yuval Filmus Aug 29 '17 at 14:58
  • $\begingroup$ @YuvalFilmus are your relying on prior knowledge of the modulus operator to trim complexity by n? $\endgroup$ – A.Rashad Aug 29 '17 at 15:00
  • $\begingroup$ What do you mean by "prior knowledge"? We all know what the modulus operator does, it's part of the semantics of C. $\endgroup$ – Yuval Filmus Aug 29 '17 at 15:01
  • $\begingroup$ True, I didn't think it over to eliminate values of j % i != 0 $\endgroup$ – A.Rashad Aug 29 '17 at 15:03
  • $\begingroup$ "how many times (at most) will your code run compared to input." It'll run once... $\endgroup$ – David Richerby Aug 29 '17 at 16:23

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