Олимпиадный тренинг

Задача . Расчет асимптотики - 7


Задача

Темы:
Для приведенного ниже кода, найдите асимптотику:
void f(vector arr)
{
    int   n = arr.size();

    vector d;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for(int j=1;j*j <=arr[i];j++)
            if (arr[i] % j == 0) {
                cnt++;
                if (arr[i] / j != j)
                    cnt++;
            }
        d.push_back(cnt);
    }
    for (int i = 0; i < d.size(); i++)
        cout << d[i] << ' ';
}

Учитывая, что элементы массива arr не превосходят C

1) O(nC)
2) O(n*sqrt(C))
3) O(n*sqrt(n))
4) O(C*sqrt(n))

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя