2

What would be the time complexity of this function

bool prime(int n) {
    if(n <= 1) {
        return false;
    } else if(n <= 3) {
        return true;
    } else if(n % 2 == 0 || n % 3 == 0) {
        return false;
    } else {
        for(int i = 5; i * i <= n; i += 6) {
            if(n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
    }
    return true;
}

If I had to guess, it would be

O(sqrt(log(n)))
Greg
  • 69
  • 6

1 Answers1

1

Each if is constant time.

for loop is executed until i * i reaches n this means it is executed sqrt(n) / 6 times. So complexity is O(sqrt(n)).

It doesn't meter that density of prime numbers is proportional to 1/log(n) (probably this is source of log(n) in your solution.

Note that time complexity (no adjective) usually is consider as worst time complexity:

Time complexity - Wikipedia

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity

Average time complexity is much harder to compute in this case. You would have to prove how fast loop terminates on average when n is not a prime number.

Marek R
  • 32,568
  • 6
  • 55
  • 140
  • But if it is ```O(sqrt(n))``` if I change the ints to long longs, and I have n as ```1020100101111191```, it runs really fast. Each second, the computer should on average run about ```10^8``` operations. This number is 16 digits long, and should run in about 1 second, but it runs almost instantly, and tells me that it is a prime number. – Greg Jul 14 '20 at 14:41
  • The density of primes does matter: when the `return false;` path is taken, the `for` loop exits earlier, reducing the time complexity. You may call `O(sqrt(n))` worst case complexity, but I don't think it's valid average time complexity. – Jeffrey Jul 14 '20 at 15:02
  • 1
    @Jeffrey complexity is always calculated for worst case scenario. So in this case when `n` is prime. Note that notation `O` means asymptotic complexity not slower then. – Marek R Jul 14 '20 at 15:35
  • Definitely not always. https://en.wikipedia.org/wiki/Average-case_complexity in case of primality testing, when you know that most cases won't be worst-case, it makes sense to consider the average case. – Jeffrey Jul 14 '20 at 15:38
  • Without adjective: [Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity](https://en.wikipedia.org/wiki/Time_complexity) – Marek R Jul 14 '20 at 15:48
  • You're assuming of course that `i * i` is O(1). A reasonable assumption for typical values of `i` and typical programming languages but not guaranteed. – Mark Ransom Jul 14 '20 at 15:58
  • I believe this is correct in complexity with regard to n. Primality testing usually is expressed with regard to the number of input bits, where it is more obvious that (as expected), trial division is exponential time. – DanaJ Jul 15 '20 at 01:55
  • @Greg, you should run it in a loop. Using the method here on your input number takes about 87ms. Using efficient BPSW is literally 10,000x faster (it is deterministic for 64-bit inputs). When considering the average case, of course we want to preface a test with a little trial division because on average it works very quickly (half of all arbitrary integers are even, for example). – DanaJ Jul 15 '20 at 02:26