Time Complexity of this primality test function

Question

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)))

Rost

I have an impression that it's O(n)? – Automate

But just the for loop takes at most O(sqrt(n)) – Rost

I think the lose bound is O(sqrt(n)) while a tighter bound would be O(sqrt(n) * 1/6). not an expert, might be entirely wrong. – Eighteen

May I ask where does the log come from? – Ozonosphere

@Automate while that's technically correct, Greg has a point. – Eighteen

@Eighteen That constant shouldn't matter in big O notation. – Ozonosphere

But is it even correct? Don't you have to test (i + 4) as well? – Maze

My bad. I'm a bit rusty. – Rost

Since all prime numbers follow the general formula 6n + 1 or 6n + 5 where n is a number, we don't have to check (i + 4) – Rost

Interesting, I'd never heard that rule before. – Maze

@Ozonosphere You're right. It doesn't matter but I am under the impression that we can always denote a slightly tighter bound and it still doesn't significantly change its meaning. – Eighteen

@MarkRansom Once known, it's pretty easy to prove primes.utm.edu/notes/faq/six.html ;) – Ozonosphere

You check 5,7, and 11 twice :) – Pahang

Answer 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.

Ferromagnetic

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. – Rost

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. – Fideicommissum

@Fideicommissum 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. – Ferromagnetic

Definitely not always. 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. – Fideicommissum

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 – Ferromagnetic

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. – Maze

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. – Optical

@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). – Optical