0
isPrime(n)
int i = 3; 
if n == 2 
return true
if n % 2 == 0 
return false; 
while i^2 <= n
  if n % i == 0
  return false
  else i+=2
return true

I think it's O(n^0.5) because of while. Am I right? Is there a way to mathematically find T(n) using sigma?

user260541
  • 1
  • 1
  • 3
  • Yes, that's right. More on that on [this question](https://stackoverflow.com/q/5811151/2950032) – maazadeeb Oct 26 '21 at 16:15
  • Why are you returning `false` for `n==2`? And why are you returning `true` for `n == 1`. It should be vice versa. Modern math doesn't consider `1` to be a prime. But it certainly sees `2` as the first (and only even) prime. But other than that, your assumption is correct. – derpirscher Oct 26 '21 at 16:19
  • Your code doesn't use recursion, so you can just straightforwardly find O() as the number of iterations of the loop (which you found). ``T(n) = 1T(n^.5)+C`` – Sean AH Oct 27 '21 at 04:51

0 Answers0