Why is the second solution faster than the first?

Question

First:

boolean isPrime(int n) {
    if (n < 2)
        return false;
    return isPrime(n, 2);
}

private boolean isPrime(int n, int i) {
    if (i == n)
        return true;
    return (n % i == 0) ? false : isPrime(n, i + 1);
}

Second:

boolean isPrime(int n) {
    if (n < 0) n = -n;
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    return rec_isPrime(n, 3);
}

boolean rec_isPrime(int n, int div) {
    if (div * div > n) return true;
    if (n % div == 0) return false;
    return rec_isPrime(n, div + 2);
}

Please explain why is the second solution better than the first. I offered the first solution in an exam and my pointes were recudec under the claim that the solution is not effecient. I want to know what is the big differene

The second stops at the square root of n. – uselpa Mar 03 '16 at 09:25 — uselpa, Mar 03 '16 at 09:25
Also, it only tests odd divisors (except 2). – uselpa Mar 03 '16 at 09:25 — uselpa, Mar 03 '16 at 09:25

score 1 · Accepted Answer · answered Mar 03 '16 at 10:18

So this is a test question and I always keep in mind some professors have a colorful prerogative, but i could see a few reasons one might claim the first is slower:

when calculating primes you really only need to test if another primes are factors. The second so seeds with an odd, 3, then adds 2 ever recursive call which skips checking evens factors and reduces the numbers of calls needed by half.
and as @uselpa pointed out, the second code snippet stops at the when the testing factor's square is greater than n. Which effectively means in this version that all odd's between 1 and n have been accounted for. This allows deducing n is prime faster than the first which counts all the way up to n before declaring prime.
may argue that since the first tests for evens inside the recursive function instead of the outer method like the second, is it is an unnessary method on the call stack.
I have also seem some claims that ternary operations are slower than if-else checks, so you professor may fall into this belief. [Personally, I am not convinced there is a performance difference.]

Hope this helps. Was fun to think about some primes!

score 0 · Answer 2 · edited May 23 '17 at 12:23

0

The first solution has a complexity of O(n) as it takes linear time, the second solution takes O(sqrt(n)) due to this line of code : if (div * div > n) return true;, because to look for a divisor past the square root is not required. For more details about that you can check : Why do we check up to the square root of a prime number to determine if it is prime?

edited May 23 '17 at 12:23

Community

1
1

answered Mar 03 '16 at 12:40

uSeemSurprised

1,826
2
15
18

Why is the second solution faster than the first?

2 Answers2