CODEWITHSUNDEEP
c++big-oasymptotic-complexity
user8371266
user8371266

Reputation:

Check if prime big-o

My original function to determine if a number was prime was:

bool is_prime(int x) {
    for (int y = 2; y < x; ++y) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

This ran with a complexity of O(x) as you may have had to go to x.

I've learned of some optimizations and need a check on my big-o. Here is the improved program:

bool is_prime(int x)
{   
    if (x % 2  == 0 && x > 2) {
        return false;
    }
    for (int y = 3; y*y <= x; y += 2) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

Does the fact that I am now going up to the sqrt() change this to O(sqrt(x))?

Upvotes: 4

Views: 2138

Answers (2)

Kashif Faraz Shamsi
Kashif Faraz Shamsi

Reputation: 511

Absolutely, The complexity of your new function is

O(sqrt(x))

But still, there is some room for optimization. Have a look at the code mentioned below:

bool isPrime(int n)
{
    // Boundary cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59253

Yes, but here are no ns. The complexity of your new function is O(sqrt(x)). When you say O(N) and don't specify what N is, it's generally taken to be the size of the input. This is confusing for functions that take a single number argument, so in those cases you should be explicit.

Upvotes: 7

Related Questions