4

Here is the code:

int foo(int n)
{
    if(n == 1)
        return 1;
    int f = 0;
    int i;
    for(i=1; i*i<=n; i++)
        if(n%i == 0)
            f+=2;
    i--;
    if(i*i == n)
        f--;
    return f;
}

My problem is that I cannot determine Θ for this for loop,
I think it's square-root(n) but is there an order named square root n?

My answer is:
Theta(sqrt(n)) because of this loop

for(i=1; i*i<=n; i++) 

i * i <= n take sqrt for both sides

i <= sqrt(n)

Correct me if I am wrong!

4

1 に答える 1