государственная разница во временных сложностях?

Question

int prime(ll n)
{
    for(int i=2;i<=sqrt(n);i++){
        if(n%2==0){
            return 0;
        }
    }
    return 1;
}


int prime(ll n)
{
    if(n<2)
        return 0;
    else if(n==2)
        return 1;
    if(n%2==0)
        return 0;
    for(int j=3; j*j<=n; j+=2)
    {
        if(n%j==0)
            return 0;
    }
    return 1;
}

Может кто-нибудь сказать, пожалуйста, разницу между сложностями во времени этих функций? Поскольку использование вышеупомянутой функции в моем коде, это дает мне неправильный ответ в проблеме codeforces round # 142 Div 2. Но выбор второй функции дает мне правильный ответ. Почему ??