```
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_{3}𝑖 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_{3}𝑛

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

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