0

What is the time complexity of this algorithm?

void prime(int n) { 
    int i = 2;
    while ((n % i) && i <= sqrt(n))
        i++;

    if (i > sqrt(n))
        print(“%d is a prime number\n”, n);
    else
        print(“%d is not a prime number\n”, n);
}
Vincent_Bryan
  • 178
  • 10
  • 5
    Why do you think `n` being prime or not prime would change the complexity? – Paul Sep 13 '16 at 02:53
  • yap, I know the complexity won't change no matter n is prime or not. So I have no idea about its complexity. – Vincent_Bryan Sep 13 '16 at 03:06
  • So what exactly are you asking? Your comment directly contradicts the first line of your question. – Disillusioned Sep 13 '16 at 03:18
  • If you restrict it to the domain of non-prime positive integers, you are guaranteed to terminate early at the smaller factor, which could be (worst case) sqrt(sqrt(n)). So yes, it would change. – Kenny Ostrom Sep 13 '16 at 04:28

2 Answers2

1

The complexity is approximately O(sqrt(N)). Some books will express that as O(N0.5).

The square root is re-computed each iteration of the loop. This is a fairly slow operation, so it's slower than optimal, but only by a constant factor, so it doesn't affect the computational complexity.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Since it is a c++ fixed size integer, yes. Although sqrt need not be constant if it had been e.g. python, or a large integer type from a math library. – Kenny Ostrom Sep 13 '16 at 04:30
0

Earlier I was thinking wrong. Hey it is simply O(sqrt(n))... Look the while contion executes for all x<=sqrt(n) which divides n. So i can atmost run O(sqrt(n)) times. So yea it is O(sqrt(n)). No other factors involved.

user2736738
  • 30,591
  • 5
  • 42
  • 56