Check if prime big-o

Question

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

Answer 1

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.