Давайте повторим технику оценки вложенных циклов. Нужно выписать ряд, в котором i-ое слагаемое — это количество итераций внутреннего цикла, на i-ой итерации внешнего.

Но на этот раз арифметической или геометрической прогрессией вам не отделаться. Чтобы правильно оценить сложность приведённого ниже кода, вам, вероятно, даже придется поискать информацию в интернете об этой последовательности.

void Harmonic(int n)
{
	var c = 0;
	for (int step = 1; step < n; step++)
		for (int i = 0; i < n; i += step)
			c++;
}

1. Какая сложность у Harmonic? 1 балл

Θ(log(n))

Θ(n)

Θ(n sqrt(n))

Θ(n log(n))

Θ(n log²(n))

Θ(n²)