CODEWITHSUNDEEP
algorithmtime-complexitybig-o
user9132502
user9132502

Reputation: 385

What is the time complexity of the algorithm to check if a number is prime?

I need to find what is the time complexity of an algorithm that checks if an integer is prime? This algorithm is a bit different in that it uses a while loop to accomplish its task

Here's the method in Java:

    public static boolean isPrime(int num) {
        int i = 2;
        boolean isPrime = false;

        while(num % i != 0) {
            i += 1;
        }

        if (num == i) {
            isPrime = true;
        }

        return isPrime;
    }

For the while loop, I have one comparison and I have one if statement outside the loop, the if statement will always be ran once so O(1). Now what is big-O of the while loop? Is it O(n)?

Upvotes: 1

Views: 5197

Answers (2)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521914

Your method may have some slight problems (addressed below), but your approach should be O(n), where n is the value/size of the input to isPrime(). That is, in this brute force method, you are basically just cycling through every possible value less than the input to find an exact match.

I would rewrite as:

// assuming positive integers only
public static boolean isPrime(int num) {
    if (num == 1) return false;

    boolean isPrime = true;

    for (int i=2; i < Math.sqrt(num); ++i) {
        if (num % i == 0) {
            isPrime = false;
            break;
        }

    return isPrime;
}

I check if the input be 1, in which case it is not a prime number. Also, this approach has the added benefit of that it only checks up to sqrt(num) for possible divisors. Any divisor greater than that cannot possibly divide evenly, so there is no point in checking. If we find a divisor, then we break from the for loop.

Upvotes: 3

spiralarchitect
spiralarchitect

Reputation: 910

Yes, it is O(N). Where N is num.

Upvotes: 1

Related Questions