Как решить T (n) = 5T (n / 2) + n ^ 2, T (1) = 2 рекурсивно

Question

Как найти асимптотическую верхнюю границу для T (n) = 5T (n / 2) + n ^ 2, T (1) = 2 без использования основной теоремы.

Вот мои шаги, ноЯ не знаю, как справиться с суммированием в конце, и поэтому не могу найти ответ "большой-O" для этой функции рекурсии.

T(n) = 5T(n/2) + n^2
     = 5^2 T(n/2^2) + 5(n/2)^2 + n^2
     = 5^3 T(n/2^3) + 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
     = ...
     = 5^i T(n/2^i) + 5^i(n/2^i)^2 + ...+ 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
     = 5^i T(n/2^i) + n^2 Sum of k from 0 to i, (5/4)^k

Как справиться с суммированием?Спасибо.

Answer 1

Как справиться с суммированием?

В сумме вы описываете геометрическую прогрессию [wiki] .Такая сумма в виде:

 n
---
\     i
/    a
---
i=0

имеет известное решение:

 n
---           n+1
\     i      a    - 1
/    a     = --------
---            a - 1
i=0

Так вот ваша сумма:

Сумма k от 0 до i, (5/4) ^ k

равно:

4 * ((5/4)^(i+1) - 1)

Мы знаем, что i ограничено log ₂ n , и этого должно быть достаточно для решения уравнения.