What will be the time complexity for the following code?

What will be the time Complexity ?

1 Like

Time Complexity apart. What if the input is 49? What will your program output?
Your Program should have been this.

if n % i == 0 or n % (i + 2) == 0:
    return "Number is not Prime"
    i += 6

The time complexity of the code is O(\sqrt{n}), which can be confirmed from the following two statements.


And Yes for n = 49 , Output will be —> “Number is not Prime”

Isn’t 49 the square of 7?

@bal_95 Sorry I forgot to add one statement in the Code, I have edited it above ,now it works fine.

Sorry @suman_18733097 I forgot to add one statement in the code, I have edited the code above, now it works fine, please have a look now.

No Definintely not, if you take n = 49, for the first time i = 5, then it will check whether
i x i = 25 <= 49 which is true so i will get incremented by 6, so now i = 11, then again it will check whether
i x i = 121 <= 49, so this will be false, so it will enter only once in the for loop and will check the for loop condition twice, so it will be O(2) , but I can’t really make the formula out of it , it will be something around o(log(n)), but not exactly log(n).
So it’s not O(underroot(n)) for sure , you can check that for any test case, it will be way less than O(underroot(n)).

The time complexity is and will be O(\sqrt{N}). Logarithmic time complexity is for Miller-Rabin Primality test. But for trial division, it is and will be O(\sqrt{N}), no matter you increment by any constant.

You cannot approximate time complexity for smaller values of N. For smaller values of N, Log(N) and \sqrt{N} are almost the same.

The worst case inputs for trial division are pseudoprimes and primes. Try finding whether 998244359987710471 is prime or not, using Trial division. According to you if it is a Logarithmic algorithm, it would instantly give the result. But it takes more time for trial division.

Feel free to ask if you still have any doubts.

1 Like

Yeah you are right, btw there are many types of Primality Test, which ones should I learn ?

Trial Division and Miller-Rabin are enough, I guess. Refer this for more info

1 Like

Quite Agree with this as Exact Execution time for any program and Time-Complexity of the Program are two different things.

As Worst Time Complexity is Upper-Bound so yeah it will always be sqrt(N)

1 Like