**New course!**Every coder should learn

**Generative AI!**

0

# Complexity of code , Optimisation

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; }

9 Answers

+ 3

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.

+ 1

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.

+ 1

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?

+ 1

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.

0

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;
}

0

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

0

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;
}

0

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

0

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