Time complexity

Question

Worst case time complexity of following code? Please explain in detail.

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("*");
            }
}

Comments

O(n⁴) seems correct, given answer is wrong.

---

This question is from Data structures made easy by narasimha karumanchi. 

I still think answer is n^5

---

https://stackoverflow.com/questions/35471781/why-is-the-runtime-of-this-code-on5

Answer 1

yes its O(n^4)

we can take O(n^5) as it is tightest upper bound only if O(n^4) is not an option

 

i loop will be running n times

j loop runs in n^2 times

k loop runs at n/2 times

total = n^4/2 = O(n^4)

correct me if i am wrong

Comments

Can anyone​ show the implementation ? How we obtain O(n^4)?

It is not clear to me. My answer stuck at O(n^3)