Доказательство индукции $ T (n) = 9T (n / 3) + n ^ 2 $

Question

Как я могу доказать, что повторение

T (n) = 9T (n / 3) + n ²

приводит к T (n) = O (n ² log (n)) с использованием метода подстановки и доказательства по индукции? Мне не разрешено использовать основную теорему.

Используя индукцию и предполагая, что T (n) ≤ cn ² log n, я пришел к следующему пункту:

T (n) = 9 * T (n / 3) + n ²

≤ 9 c (n ² / 9 + log ( n / 3)) + n ²

= cn ² + 9 c log (n / 3) + n ²

Спасибо.

Answer 1

Я думаю, вы допустили математическую ошибку при подстановке. Если предположить, что T (n) ≤ cn ² log n, то мы получим

T (n) = 9T (n / 3) + n ²

≤ 9 (c (n / 3) ² журнал (n / 3)) + n ²

= 9 ((1/9) cn ² log (n / 3)) + n ²

= cn ² log (n / 3) + n ²

На этом этапе вы очень близки к завершению работы. В качестве подсказки предположим, что логарифм является логарифмом по основанию 3. Что произойдет, если вы затем используете свойства логарифмов для упрощения cn ² log (n / 3)?