A little help finding the complexity of time and and complexity of space

50 views Asked by At
int f2(int n)
{    
    int x, y, z = 0, i;

    for(x = n, i = 0; i < n; i ++, x *= n)
    {
        y = x;
        while (y > 1)
        { 
            y /= 3;
            z += y;
        }
    }
return z;
}

I get confused by the first loop and my problem is that I can’t figure out how many times the loop is executed and how x influences the code in general.

1

There are 1 answers

4
Safwan Hijazi On BEST ANSWER

It's:

log3(n) + log3(n2) + ... + log3(nn) = log3(n)n(n+1)/2

in short term:

n^2log(n)