ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 40

Рассмотрим следующее рекуррентное соотношение.

Какой из следующих вариантов правильный?
(А) Т(n) = Θ(n ^5/2 )
(Б) T(n) = Θ(nlogn)
(С) Т(n) = Θ(n)
(D) T(n) = Θ((logn) ^5/2 )

Ответ: (С)
Объяснение: Учитывая, рекуррентное соотношение можно записать как,
Т(п) = Т(п/2) + Т(2п/5) + 7п
Т(п) = Т((5/2)п/5) + Т(2п/5) + 7п

Поскольку сумма числителя (5/2+2 = 4,5) меньше знаменателя (5), поэтому временная сложность будет самой функцией.

Следовательно, T(n) = Θ(7n) = Θ(n)
Викторина этого вопроса