big o - Time complexity of dependent and conditional triple for-loop

Question

for i in xrange(1,n+1):
    for j in xrange(1,i*i):
        if j%i==0:
            for k in xrange(0,j):
                print("*")

What will be the time complexity of the above algorithm?

Answer 1

It sounds like a homework problem, but is very interesting so I'll take a shot. We will just count number of times that asterisk is printed, because it dominates.

For each j, only those that are divisible by i trigger the execution of the innermost loop. How many of them are there? Well, in range [1, i*i) those are i, 2*i, 3*i, ..., (i-1)*i. Let's go further. k iterates from 0 to j, so first we will have i iterations (for j=i), then 2*i (for j=2*i), then 3*i.. until we iterate (i-1)*i times. This is a total of i + 2*i + 3*i + (i-1)*i printed asterisks for each i. Since i goes from 0 to n, total number of iterations is sum of all i + 2*i + 3*i + (i-1)*i where i goes from 0 to n. Let's sum it up:

Here we used multiple times the formula for sum of first n numbers. The factor which dominates in the final sum is obviously k^3, and since the formula for sum of first n-1 cubes is

,

the total complexity is O(n^4).