Calulating time complexity of loops with in loops example

Question

hi I was working with analysis of iterative solution, here is one problem that I am not able to calculate the worst-case running time

void function(int n)
{
    int count = 0;
    for (int i=0; i<n; i++)
    {
        for (int j=i; j< i*i; j++)
        {
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }
        }
    }
}

Here is the link to above problem, https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/

Please see problem no 7.

What is the time complexity of above function? In the problem, they say it is O(n^5) but I have some doubts about it can somebody provide me some mathematical proof

Answer 1

First of all, your program will crash because if(j % i == 0), both i and j are 0
changing your code a bit

void function(int n)
{
    int count = 0;
    for (int i=1; i<n; i++) // runs O(n) times
        for (int j=i; j< i*i; j++)  
            if (j%i == 0) // runs O(i) times
            {
                for (int k=0; k<j; k++) // runs j times, whenever j is factor of i
                    //that is when j = i, j = 2i ... j = i* i
                    printf("*");
            }
}

take an example when i = 5

This implies total complexity is

for (int j=5; j< 25; j++)  
     if (j%i == 0) // runs O(i) times
     {
      // runs j times when j = 5, 10, 15, 20
            for (int k=0; k<j; k++) {
                printf("*"); // runs j times when j =  5(1 + 2 + 3+ 4)
               // runs  j times which is i*i*(i*(i-1)/2) times
               // runs i^4 times
            }
     }

this implies total complexity is O(n^4)