Time Complexity of a iterative program [duplicate]

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++)
sum++;


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.

• This is not a recursive program. – adrianN Aug 29 '17 at 14:20
• oh sorry! it's iterative program – Manu Thakur Aug 29 '17 at 14:24
• Please do not use images when you could use text instead. – Tom van der Zanden Aug 29 '17 at 14:24
• 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? – Tom van der Zanden Aug 29 '17 at 14:25
• sure, no it's not duplicate of that question. – 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)$.

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)

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