Строго говоря, асимпототическая оценка сложности Add — Θ(n), потому что иногда вызов Add приводит к копированию всего массива. Однако в среднем Add работает как бы за Θ(1), потому что копирование случается очень редко.

Чтобы узаконить это "как бы за Θ(1)" придумали новый термин — амортизационная оценка сложности — это асимптотическая оценка усреднённого количество элементарных операций, которое выполняется при каждом вызове метода.

То есть более корректно говорить так: при последовательных вызовах Add, этот метод имеет амортизационную оценку сложности Θ(1).

Заметим, что если бы массив рос не в два раза, а на сколько-нибудь элементов, амортизационной оценки Θ(1) у метода Add не получилось бы. Поэтому паттерн «расти в два раза» так важен. Правда константа 2 тут не принципиальна — расти можно и в полтора и в три раза, асимптотика от этого не поменяется.

Со всеми этими знаниями, оцените сложность этого кода:

List<int> GetCompoundNumbers(int n)
{
	var list = new List<int>();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++)
			list.Add(i * j);
	return list;
}

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

Θ(n)

Θ(n log(n))

Θ(n²)

Θ(n² log(n))

Θ(n³)