Time Complexity of a iterative program [duplicate]

Question

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.

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

Answer 1

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

Answer 2

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 n² times, that makes an O(n²) 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 n² , that should make the inner most loop of O(n²)

That makes the overall complexity = n × n² × n² = n⁵ i.e. O(n⁵) not O(n⁴)