What is the time complexity of the following function

Calculate time complexity of:

void func(int n)
{
    int sum=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=i*i;j+=i)
        {
            sum+=i;
        }
    }
}

I think the time complexity is O(n^2) because the outer loop runs n times, and the inner loop runs approximately i times for each value of i, that means the inner loop will run 1+2+3+…+n times, which is O(n^2), however, Google Bard says that the complexity is O(n^3) because the nesting has a multiplicative effect on the time complexity, meaning the actual amount of iterations is

n*(1+2+3+…+n) which is O(n^3)

But how is that possible?

>Solution :

Your calculations are correct – it is O(n^2). The inner loop has step of i so it will run for ~ i*i/i iterations giving O(n) for inner loop too.