What is the time complexity of function2?

March 2, 2023

int function2(int n)
{
    int i, j, k;
    int sum = 0;
    for (k = 1; k <= n; k += 1)
    {
        for (i = 1; i <= n; i *= 3)
        {
            j = i;
            while (j > 1)
            {
                sum += 1;
                j /= 3; 
            }
        } 
    }
    return sum; 
}

I understand that:

The outermost for loop runs n times.
The inner for loop runs log3(n) times.
The innermost while loop runs log3(i) times, and since i increases at a rate of log3(n), the while loop runs log3(log3(n)) times?
So the total complexity is O(n * logn * log(logn))?

But thinking about it, wouldn’t the while loop run the same number of times that i has been multiplied by 3?
so couldn’t we rewrite it as:

for (k = 1; k <= n; k++)
    for (i = 1; i <= log3(n); i++)
        for (j = 0; j < i; j++)

? in which case it’d be O(n * logn * logn)?

Someone also said it was O(n * logn) because it’s a harmonic series? how is this a harmonic series?

>Solution :

So the total complexity is O(n * logn * log(logn))?

No.

wouldn’t the while loop run the same number of times that i has been multiplied by 3

Yes.

in which case it’d be O(n * logn * logn)?

Yes.

The inner most loop will loop log_₃𝑖 times for a given iteration of the middle loop, but 𝑖 is a power of 3, so actually with each next iteration of the middle loop, the inner loop will do one more iteration than before.

The number of inner loop iterations for the combined iterations of the middle loop — for one outer iteration — is the following sum:

1 + 2 + 3 + … + log_₃𝑛

This is a triangular number, and so this is O(log²𝑛).

Bringing the outer loop into the equation gives: O(𝑛log²𝑛)