Complexity of code , Optimisation | Sololearn: Learn to code for FREE!
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; }

31st Mar 2021, 11:28 AM
Maja
+ 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.
31st Mar 2021, 11:38 AM
+ 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.
31st Mar 2021, 11:51 AM
+ 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?
31st Mar 2021, 12:43 PM
+ 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.
31st Mar 2021, 1:22 PM
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; }
31st Mar 2021, 11:45 AM
Maja
0
Because , it si also sufficient to check for divisors up to half of n
31st Mar 2021, 11:46 AM
Maja
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; }
31st Mar 2021, 12:19 PM
Maja
0
No, I have not offered answers for the last two. Maybe it is n! because of recursion. I don't know.
31st Mar 2021, 1:02 PM
Maja
0