Time complexity of O(n^2)

Question

void f(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n * n / i; j += i)
            printf(“*”);
}

Whats the time complexity for this code? I figured it would be O(n³) but turns out the actual answer is O(n²) and I have no clue why. can someone explain? (there is a chance its a mistake in the exam)

Answer 1

There are two things to notice about the inner loop:

1. The "divide by i" here: j<=n*n/i

2. The "increment by i" here: j+=i (which gives another "divide by i)

Taking that into account we can see how many time the inner loop executes depending of the value of i:

i = 1 --> n*n/1/1

i = 2 --> n*n/2/2

i = 3 --> n*n/3/3

i = 4 --> n*n/4/4

....

Then make the sum:

n*n/1/1 + n*n/2/2 + n*n/3/3 + n*n/4/4 + ...

which is:

n*n/1^2 + n*n/2^2 + n*n/3^2 + n*n/4^2 + ...

which is:

n^2 * (1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + ... )

According to https://en.wikipedia.org/wiki/Basel_problem this is approx:

n^2 * 1.644934

so the complexity is O(n^2)

Just for fun the following code calculates the number of times the inner loop is executed

#include <stdio.h>

unsigned long long  f(int n)
{
    unsigned long long c = 0;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n*n/i; j+=i)
        {
            ++c;
        }
    }
    return c;
}

void g(int n)
{
    unsigned long long c = f(n);
    printf("d=%-10d c=%-10llu c/n^2=%f\n", n, c, (((double)c)/n/n));
}

int main()
{
    g(10);
    g(100);
    g(1000);
    g(10000);
    return 0;
}

Output:

d=10         c=157        c/n^2=1.570000
d=100        c=16395      c/n^2=1.639500
d=1000       c=1644474    c/n^2=1.644474
d=10000      c=164488783  c/n^2=1.644888