Решение уравнения с использованием обобщения основной теоремы

Question

Я прошу помощи в объяснении, как работает доказательство. Я видел примеры этого, но мне трудно понять это.

Докажите следующее

Решение уравнения

T (n) = aT (n / b) + Θ (n^k log^p n), где a ≥ 1, b> 1, p ≥ 0

• T (n) = O (n^{log_b a}), если a> b^k

• T (n) = O (n^k log^{p + 1} n), если a = b^k

• T (n) = O (n^k log^p (n)), если a k

Вот скриншот вопроса в лучшем формате

Это обобщение основной теоремы.

Answer 1

Для некоторого x = log (n) / log (b) n = b^x. Разделите уравнение на^х

T (b^x) / a^x = T (b^x-1) / a^x-1 + Θ ((b^k/ a)^x· x^p· log^p b)

Суммирование слагаемых m^p· q^m для m

• ограничен константой для q <1
• растет как х^{р +1} для q = 1
• доминирует последний член x^p· q^x для q > 1

Распознавание q = b^k/ a и подстановка обратно дает результат

• для a k: T (b^x) = O (a^x) или T (n) = O (n^{log_b a})
• для a = b^k: T (b^x) = O (x^{p +1}· a^x) или T (n) = O (n^{log_b a}· log^{p +1} n)
• для a> b^k: T (b^x) = O (x^p· b^kx) или T (n) = O (n^k· log^p n)