This question already has an answer here:

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.


marked as duplicate by adrianN, Tom van der Zanden, David Richerby, Evil, Raphael algorithms Aug 29 '17 at 19:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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)$.


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)

  • $\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.