1. Проверить, верны ли следующие утверждения? a) 17 = O(1); b) N logN + 5 = O(N); c) d) N3 + 2N2 = Ω(N2); 2. Пусть время работы алгоритма Т(N) = O(f(N)). Если X элементов обрабатываются за Y мс, то во сколько раз следует ожидать увеличения времени выполнения при обработке Z элементов? № варианта f(N) X Y Z 26 N3 3000 10 12000 3. Найти наиболее точную оценку для рекуррентных отношений. a) T(N) = 3T(N/2) + N, T(1) = 1; b) T(N) = 3T(N/2) + N logN, Т(N) — константа при N ≤ 8; c) T(N) = T(9N/10) + N; если Т(N) - константа при N ≤ 2; d) T(N) = 2T(N — 1) + N, T(1) = 2;