Выбор постоянной для последнего шага в способе замены $ T (N)= 5T (N / 4) + N ^ 2 $

Question

Я выяснил решение для отношения рецидива, но я не уверен, какая постоянная должна быть для последнего шага для удержания.

$ t (n)= 5t (n / 4) + n ^ 2 $

Угадайте: $ t (n)= o (n ^ 2) $

Докажите: $ t (n) \ leq cn ^ 2 $

Разбивка

$ t (n) \ leq 5 (c (n / 4) ^ 2) + n ^ 2 $

$= (5/16) cn ^ 2 + n ^ 2 $

$ \ leq cn ^ 2 $

Для последнего шага Чтобы удержаться, я не уверен, что значение C должно быть из-за (5/16).Мое предположение будет C>= 1, и я не уверен, если бы это будет держать.

Answer 1

Ваша постоянная $ C $ необходимо удовлетворить $$ \ frac {5} {16} c n ^ 2 + n ^ 2 \ leq c n ^ 2, $$ это, $$ \ frac {5} {16} C + 1 \ leq c.$$ Надеюсь, вы сможете определить набор констант $ C $ , для которого это неравенство удовлетворено.

Answer 2

$$ t (n)= 5t \ Left (\ frac {n} {4} \ справа) + n ^ 2= 5 ^ 2t \ lever (\ frac {n} {4 ^ 2} \ справа) + \ левый (\ frac {5} {16} +1 \ right) n ^ 2= \\= 5 ^ 3t \ левый (\ frac {n} {4 ^ 3} \Право) + \ левый (\ левый (\ frac {5} {16} \ справа) ^ 2 + \ frac {5} {16} +1 \ \} n ^ 2=CDOT= \\ = 5 ^ кт \ левый (\ frac {n} {4 ^ k} \ справа) + \ левый (\ левый (\ frac {5} {16} \ справа) ^ {k-1} + \ cdots + \ frac{5} {16} +1 \ верно) n ^ 2 $$ Если у вас есть некоторое начальное условие для $ t (1) $ , и мы предполагаем $ n= 4 ^ k \ leftrightarrow k=\ log_ {4} n $ , тогда мы получаем $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {16} {11} \ left (1- \ левый (\ frac {5} {16} \ справа) ^ {k-1} \ справа) \ in o (n ^ 2) $$