Какова временная сложность этого алгоритма, когда предел изменяется внутри цикла?

Question

Как рассчитать временную сложность или сложность этого алгоритма, когда неясно, сколько итераций повторяет цикл?

cin >> n;
int i = 0;
for (int j=1; i <= n; j++) {
    i += j;
}

Answer 1

Следует понимать, что ряд в j выглядит следующим образом:

1 + 2 + 3 + 4 + ... + n (not the n in your question)

Сумма этой серии определяется формулой Гаусса:

n * (n + 1) / 2

Это означает, что сумма изменяется как n^2, где n - это число слагаемых или шагов в цикле. Следовательно, цикл должен изменяться следующим образом:

O(sqrt(n))

Где сейчас n - это n из вашего кода цикла, т. Е. Верхняя граница цикла.