Big-O обозначение двух циклов, вложенных в цикл

Question

У меня работает следующий код для проверки простых пар до определенного условия (p * q <= n), и я не уверен, что для обозначения Big-O для этого будет O (n ^ 2) или O(NlogN): </p>

В main.cpp:

int main(int argc, char const *argv[]) 
{
    int n, q;
    cin >> n;

    for (int p = 0; p * (p + 2) <= n; p++)
    {
        q = p+2;
        if (isPrime(p) && isPrime(q))
            // output (p,q)
    }
    return 0;
}

bool isPrime(int n)
{
    if (n < 2)
        return false;

    for (int i = 2; i <= n / 2; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

Answer 1

Ваш главный цикл for будет масштабироваться как sqrt(n).В то время как основная функция будет линейно масштабироваться для своего входа, вход всегда приблизительно равен sqrt(n).Следовательно, общее время выполнения будет масштабироваться как n^.5 * (n^.5 + n^.5) = 2n.Так что это O(N).