What will be the time Complexity ?

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

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

Isn’t 49 the square of 7?

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.

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

Quite Agree with this as

Exact Execution time for any programandTime-Complexity of the Programare two different things.

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