Complexity of code , Optimisation

Question

Below is a function that determines whether the number is prime. The complexity of the code is O (n). Optimize the code so that its complexity is O (n½)

bool isPrime (int n)
{ if (n <= 1)
return false;
for (int i = 2; i <n; i ++)
if (n% i == 0)
return false;
return true; }

Answer 1

It is sufficient to check for divisors up to the square root of the original number. Therefore, you can change the loop condition to
for ( ...; i <= ( int )sqrt( n ); ... )
which should result in the corresponding complexity.

Answer 2

Yes, but then the complexity would be O( 1/2 * n ), and if I remember correctly, constant factors can be ignored, so O( 1/2 * n ) = O( n ). To achieve O( n ^ 1/2 ), you need to reduce the amount of iterations even further, i.e. by stopping at the square root.

Answer 3

I would be inclined to agree to your idea for 1. Since all logarithms are asymptotically equal in Big-O notation, O( n * log3 n ) = O( n * log n ), so it should be linear-logarithmic time complexity.
Do you already have assumptions for the latter two?

Answer 4

Recursive functions aren't all that different from loops. In fact, end-recursive functions can be translated into loops and vice-versa.

Looking at f1, the function subtracts a constant amount from its argument in each call. This is similar to a loop iterating the intervall [0, n] adding that constant to its counter variable each iteration. The side costs only involve adding 1, which has constant time complexity O( 1 ) = O( n ^ 0 ). Since you have a linear-recursive function without real side costs, the time complexity will be O( n ).

On the other hand, f3 reduces its argument by a constant factor each iteration. This is similar to the loop from example 1. that multiplies its counter variable by a factor each iteration. Since the side costs are once again constant, this results in logarithmic time complexity O( log n ).

Maybe the functions would be slightly less performant than a loop because a call-stack has to be built, keeping track of the returned values, but they could be rewritten to avoid that.

Answer 5

Thnks. I understand. Can you tell me what is complexity of this code:

bool isPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i < (n/2); i++)
        if (n % i == 0)
            return false;

    return true;
}

Answer 6

Because , it si also sufficient to check for divisors up to half of n

Answer 7

I understand. It's correct. Thnks very much!

can you help me to calculate complexity of these 3 codes? For 1. I think it's n*log3 n (3 is in index of log) but I m not sure.

1.

int main(){
int n;
cin>>n;
int a = n-1;
for (int i=0; i<n; i*=3){
for (int j=0; j<n; j++)
cout<<a+i<<endl;
}
return 0;
}

2.  
int f1(int n){
    if (n <= 0)
        return 1;
    else
        return 1 + f1(n-1);
}
int main(){
int n;
  cin>>n;
f1(n);
return 0;
}

3.
int f3(int n){
    if (n <= 0)
        return 1;
    else
        return 1 + f3(n/5);
}
int main(){
int n;
cin>>n;
f3(n);
return 0;
}

Answer 8

No, I have not offered answers for the last two. Maybe it is n! because of recursion. I don't know.

Answer 9

With your explanation your answer seems correct to me. Thank you very much!!!