0

Am new to time complexity analysis...

Would appreciate if someone could tell me if this is quadratic or not. And also if there's simpler way to make it o(1).

public class PrimeNumbers {
    public boolean isPrime(int n) {
        boolean retValue = true;
        for (int i = 2; i < n; i++) {
            if (n % 2 == 0) {
                retValue = false;
            }
        }
        return retValue;
    }
}

If someone could break it down why it is what it is, it will definitely help me learn. :)

Thanks a lot!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
PacificNW_Lover
  • 4,746
  • 31
  • 90
  • 144

2 Answers2

5

The worst-case runtime of this algorithm is O(n). Your algorithm works by counting up from 2 up to n (so the loop runs O(n) times) and, at each step, doing some arithmetic operations (each of which runs in time O(1)). Therefore, the overall runtime is O(n).

You can speed this up in a few ways. One way is to only count up to √n rather than n itself, since if n has any divisors at all, at least one of those divisors is a prime number. There's a cool fact that any prime divisor of a number n has to be no greater than √n, so you only need to count up to √n, inclusive. That drops your runtime to O(√n), which is a noticeable improvement.

There are other algorithms you can use to speed this up further, but they're quite complicated and only really useful for very, very large integers.

You've asked about getting this down to time O(1). Since there are only finitely many possible values that can fit into an int, one option would be to build a giant table of all the prime numbers that fit into an int, store them in a hash table, and then look up the number in question in that table. It's not elegant and its a huge memory hog, but it will work.

Depending on your use case, you might also want to check out the Sieve of Eratosthenes, which will give you a way of computing all the prime numbers up to some number n in time O(n), afterwards giving O(1) queries for any number in that range.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • I like the non elegant solution. Interesting to use for the long long int case :-) – Eyeball Jan 27 '15 at 21:41
  • "*since if n has any divisors at all, they have to be no larger than √n*" - what you wrote is generally true, but this is false. 18 is a divisor of 36 but is greater than 6 (== sqrt(36)). You meant that any pair of numbers whose multiplication result is 36 has one number equal to, or lower than the square root. – Reut Sharabani Jan 27 '15 at 21:45
  • 1
    @ReutSharabani Oh, right. I was thinking about prime divisors. Let me fix that... – templatetypedef Jan 27 '15 at 21:50
  • By the way, knowing that 2 is prime, could we start the loop at i=1, stop at i<=sqrt(n) and increment i by 2 each iteration? Would Double the speed right? – Eyeball Jan 27 '15 at 22:24
  • @Eyeball Well, you don't want to start at 1, because n % 1 = 0 for any n. :-) But yes - you could special-case 2, then check only odd numbers to cut the search time roughly in half. This doesn't change the asymptotic complexity, but it's a huge win in practice. (You could be even more clever with your odd numbers by noting that every three odd numbers is divisible by 2 and skipping those as well, and if you keep this up you can get some even larger wins.) – templatetypedef Jan 27 '15 at 22:28
  • Which is basically what that Greek guy did I realize – Eyeball Jan 27 '15 at 22:31
2

Let's look at the for loop (we'll ignore how many times it does execute and think of the worst case):

        for (int i = 2; i < n; i++) { ...

this can iterate n - 3 times which is linear with the input - this means O(n).

Some points on creating a working isPrime method:

  1. An immediate observation is, usually, that other than 2, no even numbers are primary (they all have 2 as a divisor), so we can skip all even numbers other than 2.

  2. A big improvement is also noticing that a number has no divisor greater than round(X) where X * 2 = NUMBER, so we can chop n to n/2 in the loop. This is true since any Y greater than X where X * 2 = NUMBER would gives us NUMBER / Y < 2.

  3. Another big improvement on that is to notice that divisors are paired. Paired how? well, if we were to list a numbers divisors side by side in two columns we would get a list that adds up to 36 (so we can call X and Y a pair if NUMBER / X = Y ==> X * Y = NUMBER)

List of divisors side by side:

2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
6 * 6 = 36 # is the midpoint
9 * 4 = 36
12 * 3 = 36
18 * 2 = 36

Having established that, if you take a close look you can see that from midpoint on, we're checking stuff we'd already find in case the number had any divisors. This happens because X * Y == Y * X (multiplication is commutative). This means we need to reach at most X where X * X = NUMBER, and if we solve this equation we get X = square_root(NUMBER), so we can chop the loop to only go until n's square root and we should be fine.

This is a very common problem and google will be very useful at understanding and solving it. Many optimized algorithms exist but the optimizations I wrote are the common ones any one should probably know. Good luck.

There is no O(1) solution as far as I know. Intuition says you shouldn't be able to find one.

Reut Sharabani
  • 30,449
  • 6
  • 70
  • 88